HDU 4107 Gangster
HDU
2023-09-11 14:15:28 时间
Gangster
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 410764-bit integer IO format: %I64d Java class name: Main
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.
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).
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 1 1 2 1 2 3 1
Sample Output
1 3 1
Source
解题:线段树。。时间卡死人啊。。。多交几次g++就过了
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 200010; 7 struct node { 8 int minv,maxv,lazy; 9 } tree[maxn<<2]; 10 int n,m,p; 11 inline void pushdown(int v) { 12 if(tree[v].lazy) { 13 tree[v<<1].lazy += tree[v].lazy; 14 tree[v<<1|1].lazy += tree[v].lazy; 15 tree[v<<1].minv += tree[v].lazy; 16 tree[v<<1|1].minv += tree[v].lazy; 17 tree[v<<1].maxv += tree[v].lazy; 18 tree[v<<1|1].maxv += tree[v].lazy; 19 tree[v].lazy = 0; 20 } 21 } 22 inline void pushup(int v) { 23 tree[v].maxv = max(tree[v<<1].maxv,tree[v<<1|1].maxv); 24 tree[v].minv = min(tree[v<<1].minv,tree[v<<1|1].minv); 25 } 26 void update(int L,int R,int lt,int rt,int val,int v) { 27 if(lt <= L && rt >= R && (tree[v].minv >= p || tree[v].maxv < p)) { 28 val <<= (tree[v].minv >= p); 29 tree[v].minv += val; 30 tree[v].maxv += val; 31 tree[v].lazy += val; 32 return; 33 } 34 pushdown(v); 35 int mid = (L + R)>>1; 36 if(lt <= mid) update(L,mid,lt,rt,val,v<<1); 37 if(rt > mid) update(mid+1,R,lt,rt,val,v<<1|1); 38 pushup(v); 39 } 40 void query(int L,int R,int v){ 41 if(L == R){ 42 if(L > 1) putchar(' '); 43 printf("%d",tree[v].lazy); 44 return; 45 } 46 pushdown(v); 47 int mid = (L + R)>>1; 48 query(L,mid,v<<1); 49 query(mid+1,R,v<<1|1); 50 } 51 int main() { 52 int a,b,c; 53 while(~scanf("%d %d %d",&n,&m,&p)){ 54 memset(tree,0,sizeof tree); 55 while(m--){ 56 scanf("%d %d %d",&a,&b,&c); 57 update(1,n,a,b,c,1); 58 } 59 query(1,n,1); 60 putchar('\n'); 61 } 62 return 0; 63 }
相关文章
- hdu 1004 Let the Balloon Rise
- hdu 2476 String painter 区间DP
- hdu 1576 A/B
- 【hdu 6438】Buy and Resell
- 【hdu 6000】Wash
- 【hdu 3032】Nim or not Nim?
- 【hdu 1847】Good Luck in CET-4 Everybody!
- 【 2017 Multi-University Training Contest - Team 9 && hdu 6162】Ch’s gift
- HDU 4403 A very hard Aoshu problem (DFS暴力)
- hdu 2052 Picture(java)
- HDU 3037 Saving Beans (Lucas法则)
- HDU 4912 lca贪心
- HDU 3853 期望概率DP