fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ff first
  5. #define ss second
  6. #define all(a) a.begin(), a.end()
  7. const int N = 1e6;
  8. int n, Q, M, cnt = 0, emp = 1;
  9. int version[300010];
  10. long long tree[N], lazy[N]; 
  11. int Left[N], Right[N];
  12. //map<int, int> Left, Right;
  13. //#define int long long
  14.  
  15. void build(int v, int vl, int vr){
  16. 	if(vl == vr){
  17. 		tree[v] = 0LL, lazy[v] = 0LL;
  18. 		return;
  19. 	}
  20. 	Left[v] = emp++; 
  21. 	Right[v] = emp++;
  22. 	int mid = (vl + vr)>>1;
  23. 	build(Left[v], vl, mid);
  24. 	build(Right[v], mid+1, vr);
  25. //	tree[v] = (tree[Left[v]] + tree[Right[v]]);
  26. }
  27. int push(int v, int vl, int vr, long long x){
  28. 	int NEW = emp++;
  29. 	Left[NEW] = Left[v], Right[NEW] = Right[v];
  30. 	lazy[NEW] = lazy[v] + x;
  31. 	tree[NEW] = tree[v] + (long long)((vr-vl+1)*x*1LL);
  32. 	return NEW;
  33. }
  34. int add(int l, int r, long long x, int v, int vl, int vr){
  35. 	if(lazy[v]){
  36. 		if(vl != vr){
  37. 			int smid = (vl +vr)>>1;
  38. 			Left[v] = push(Left[v], vl, smid, lazy[v]);
  39. 			Right[v] = push(Right[v], smid+1, vr, lazy[v]);
  40. 		}
  41. 		lazy[v] = 0LL;
  42. 	}
  43. 	if(l > vr or vl > r) return v;
  44. 	int NEW = emp++;
  45. 	if(l <= vl and r >= vr){
  46. 		tree[NEW] = tree[v] + (long long)((vr-vl+1)*x*1LL);
  47. 		lazy[NEW] = x;
  48. 		Left[NEW] = Left[v], Right[NEW] = Right[v];
  49. 		return NEW;
  50. 	}
  51. 	int mid = (vl + vr)>>1;
  52. 	Left[NEW] = add(l, r, x, Left[v], vl, mid);
  53. 	Right[NEW] = add(l, r, x, Right[v], mid+1, vr);
  54. 	tree[NEW] = (tree[Left[NEW]] + tree[Right[NEW]]);
  55. 	return NEW;
  56. }
  57. long long get_sum(int l, int r, int v, int vl, int vr){
  58. 	if(lazy[v]){
  59. 		if(vl != vr){
  60. 			int smid = (vl +vr)>>1;
  61. 			Left[v] = push(Left[v], vl, smid, lazy[v]);
  62. 			Right[v] = push(Right[v], smid+1, vr, lazy[v]);
  63. 		}
  64. 		lazy[v] = 0LL;
  65. 	}	
  66. 	if(l > vr or vl > r) return 0LL;
  67. 	if(l <= vl and r >= vr){
  68. 		return tree[v];
  69. 	}
  70. 	int mid = (vl + vr)>>1;
  71. 	tree[v] = (tree[Left[v]] + tree[Right[v]]);
  72. 	return get_sum(l, r, Left[v], vl, mid) + get_sum(l, r, Right[v], mid+1, vr);
  73. } 
  74. // 
  75. main(){
  76.    ios::sync_with_stdio(0);
  77.    cin.tie(0); cout.tie(0);
  78. 	cin >> n >> Q >> M;
  79. 	version[cnt] = emp++;
  80. 	build(version[0], 1, n);
  81. 	cnt++;
  82. 	while(Q--){
  83. 		int l, r, x; cin >> l >> r >> x;
  84. 		version[cnt] = add(l, r, x,version[cnt-1], 1, n); 
  85. 		cnt++;
  86. 	}
  87. 	while(M--){
  88. 		int pos; long long x; cin >> pos >> x;
  89. 		if(get_sum(pos, pos,version[cnt-1], 1, n) >= x){
  90. 			int l = 1, r = cnt;			
  91. 			if(get_sum(pos, pos,version[1], 1, n) >= x){
  92. 				cout << 1 << '\n';
  93. 				continue;
  94. 			}
  95. 			for(int round = 1; round <= 23 and l < r; round++){
  96. 				int mid = (l + r)>>1;
  97. 				if(get_sum(pos, pos,version[mid], 1, n) >= x){
  98. 					r = mid;
  99. 				}else l = mid;
  100.  
  101. 			}
  102. 			r = min(r, cnt-1);
  103. 			cout << r << '\n';
  104. 		}else cout << "-1" << '\n';
  105. 	}
  106. 	return 0;
  107. }
Runtime error #stdin #stdout 0.07s 152176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hyMNpe
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!