2015
04-16

# Gangster

There are two groups of gangsters fighting with each other. The first group stands in a line, but the other group has a magic gun that can shoot a range [a, b], and everyone in that range will take a damage of c points. When a gangster is taking damage, if he has already taken at least P point of damage, then the damage will be doubled. You are required to calculate the damage that each gangster in the first group toke.
To simplify the problem, you are given an array A of length N and a magic number P. Initially, all the elements in this array are 0.
Now, you have to perform a sequence of operation. Each operation is represented as (a, b, c), which means: For each A[i] (a <= i <= b), if A[i] < P, then A[i] will be A[i] + c, else A[i] will be A[i] + c * 2.
Compute all the elements in this array when all the operations finish.

The input consists several testcases.
The first line contains three integers n, m, P (1 <= n, m, P <= 200000), denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).

The input consists several testcases.
The first line contains three integers n, m, P (1 <= n, m, P <= 200000), denoting the size of the array, the number of operations and the magic number.
Next m lines represent the operations. Each operation consists of three integers a; b and c (1 <= a <= b <= n, 1 <= c <= 20).

3 2 1
1 2 1
2 3 1

1 3 1

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 200005;
struct Tnode{				// 一维线段树
int l, r, min, max, add;
int len() { return r - l;}
int mid() { return MID(l,r);}
bool in(int ll,int rr) { return l >= ll && r <= rr; }
void lr(int ll,int rr){ l = ll; r = rr;}
};
Tnode node[MAX<<2];
int P, n;
void Build(int t,int l,int r)
{
node[t].lr(l,r);
node[t].min = node[t].max = node[t].add = 0;
if( node[t].len() == 1 )
return ;
int mid = MID(l,r);
Build(L(t),l,mid);
Build(R(t),mid,r);
}

{
}

{
{

}
}

void Updata(int t,int l,int r,int add)
{
if( node[t].in(l,r) )
{
if( node[t].max < P )
{
return ;
}
else
if( node[t].min >= P )
{
return ;
}
}
if( node[t].len() == 1 ) return ;
int mid = node[t].mid();
if( l < mid ) Updata(L(t),l,r,add);
if( r > mid ) Updata(R(t),l,r,add);

node[t].min = min(node[L(t)].min, node[R(t)].min);
node[t].max = max(node[L(t)].max, node[R(t)].max);
}

void Query(int t)
{
if( node[t].min == node[t].max )
{
FOR(i, node[t].l, node[t].r)
printf(i == n-1 ? "%d\n" : "%d ", node[t].min);
return ;
}
if( node[t].len() == 1 ) return ;
int mid = node[t].mid();
Query(L(t));
Query(R(t));
}

int main()
{
int m, x, y, val;

while( ~scanf("%d%d%d", &n, &m, &P) )
{
Build(1, 0, n);
while( m-- )
{
scanf("%d%d%d", &x, &y, &val);
Updata(1, x-1, y, val);
}
Query(1);
}

return 0;
}


1. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count