首页 > 代码库 > hdu 4107

hdu 4107

2024-08-13 00:14:05   215人阅读

Gangster

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3123    Accepted Submission(s): 762


Problem Description
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.
 

 

Input
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).
 

 

Output
Print A[1] to A[n] in one line. All the numbers are separated by a space.
 

 

Sample Input
3 2 11 2 12 3 1
 

 

Sample Output
1 3 1
 

 

Source
2011 Alibaba-Cup Campus Contest
 

 

Recommend
lcy   |   We have carefully selected several similar problems for you:  4104 4102 4103 4105 4106
题意不想说 ，妈的 什么破题目 ，一样的代码第一次交就过，第二次就wa
时间卡，这段时间杭电也卡，我快晕了
线段树，用c++交
  1 #include<iostream>  2 #include<cstdio>  3 using namespace std;  4 #define N 200004  5 int  n,m,p;  6 struct node  7 {  8     int left,right;  9     int max,min; 10     int num; 11 }tree[N*4]; 12 void build(int l,int r,int pos) 13 { 14     int mid=(l+r)>>1; 15     tree[pos].left=l; 16     tree[pos].right=r; 17     tree[pos].max=0; 18     tree[pos].min=0; 19     tree[pos].num=0; 20     if(l==r) 21     { 22         return ; 23     } 24     build(l,mid,pos<<1); 25     build(mid+1,r,pos<<1|1); 26 } 27 void update(int l,int r,int pos,int v) 28 { 29     int mid=(tree[pos].left+tree[pos].right)>>1; 30     if(tree[pos].left==l&&tree[pos].right==r) 31     { 32         if(tree[pos].min>=p) 33         { 34             tree[pos].min+=v<<1; 35             tree[pos].max+=v<<1; 36             tree[pos].num+=v<<1; 37             return ; 38         } 39         if(tree[pos].max<p) 40         { 41             tree[pos].min+=v; 42             tree[pos].max+=v; 43             tree[pos].num+=v; 44             return ; 45         } 46     } 47     if(tree[pos].num!=0) 48     { 49         tree[pos<<1].num+=tree[pos].num; 50         tree[pos<<1].min+=tree[pos].num; 51         tree[pos<<1].max+=tree[pos].num; 52         tree[pos<<1|1].num+=tree[pos].num; 53         tree[pos<<1|1].min+=tree[pos].num; 54         tree[pos<<1|1].max+=tree[pos].num; 55         tree[pos].num=0; 56     } 57     if(r<=mid) 58         update(l,r,pos<<1,v); 59     else if(l>mid) 60         update(l,r,pos<<1|1,v); 61     else 62     { 63         update(l,mid,pos<<1,v); 64         update(mid+1,r,pos<<1|1,v); 65     } 66     if(tree[pos*2].max>tree[pos<<1|1].max) 67         tree[pos].max=tree[pos<<1].max; 68     else 69         tree[pos].max=tree[pos<<1|1].max; 70     if(tree[pos*2].min>tree[pos<<1|1].min) 71         tree[pos].min=tree[pos<<1|1].min; 72     else 73         tree[pos].min=tree[pos<<1].min; 74 } 75 void query(int pos) 76 { 77     if(tree[pos].left==tree[pos].right) 78     { 79         if(tree[pos].left!=1) 80             printf(" "); 81         printf("%d",tree[pos].num); 82         return; 83     } 84     if(tree[pos].num!=0) 85     { 86         tree[pos<<1].num+=tree[pos].num; 87         tree[pos<<1|1].num+=tree[pos].num; 88         tree[pos].num=0; 89     } 90     query(pos<<1); 91     query(pos<<1|1); 92 } 93 int main() 94 { 95     while(scanf("%d%d%d",&n,&m,&p)>0) 96     { 97         build(1,n,1); 98         while(m--) 99         {100             int a,b,c;101             scanf("%d%d%d",&a,&b,&c);102             update(a,b,1,c);103         }104         query(1);105         printf("\n");106     }107     return 0;108 }

 

hdu 4107


联系
我们