fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890123456789LL
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. typedef long long cat;
  35.  
  36. #ifdef DONLINE_JUDGE
  37. 	// palindromic tree is better than splay tree!
  38. 	#define lld I64d
  39. #endif
  40.  
  41. struct segtree {
  42. 	struct node {
  43. 		int son[2];
  44. 		int z,k;
  45. 		int mx,ans;
  46. 	};
  47. 	vector<node> T;
  48.  
  49. 	int count(int akt, int mx_lft) {
  50. 		if(T[akt].z == T[akt].k-1) return (T[akt].mx > mx_lft);
  51. 		node n =T[akt];
  52. 		if(T[n.son[0]].mx <= mx_lft) return count(n.son[1],mx_lft);
  53. 		int ret =count(n.son[0],mx_lft);
  54. 		ret +=T[akt].ans-T[n.son[0]].ans;
  55. 		return ret;
  56. 	}
  57.  
  58. 	void constT(int akt, vector<int> &A) {
  59. 		node n =T[akt];
  60. 		if(n.z == n.k-1) {
  61. 			T[akt].mx =A[n.z];
  62. 			return;
  63. 		}
  64. 		for(int i =0; i < 2; i++) {
  65. 			if(i == 0) n.k =(n.z+n.k)/2;
  66. 			else {n.z =n.k; n.k =T[akt].k;}
  67. 			T[akt].son[i] =T.size();
  68. 			T.push_back(n);
  69. 			constT(T[akt].son[i],A);
  70. 		}
  71. 		T[akt].mx =max(T[T[akt].son[0]].mx,T[T[akt].son[1]].mx);
  72. 		T[akt].ans =T[T[akt].son[0]].ans+count(T[akt].son[1],T[T[akt].son[0]].mx);
  73. 	}
  74.  
  75. 	segtree(int N, vector<int> &A) {
  76. 		node n;
  77. 		n.son[0] =n.son[1] =-1;
  78. 		n.z =0, n.k =N;
  79. 		n.ans =1;
  80. 		T.dibs(2*N);
  81. 		T.resize(1,n);
  82. 		constT(0,A);
  83. 	}
  84.  
  85. 	void put(int akt, int pos, int val) {
  86. 		node n =T[akt];
  87. 		if(n.z > pos || pos >= n.k) return;
  88. 		if(n.z == pos && n.k == pos+1) {
  89. 			T[akt].mx +=val;
  90. 			return;
  91. 		}
  92. 		if(pos < (n.z+n.k)/2) put(n.son[0],pos,val);
  93. 		else put(n.son[1],pos,val);
  94. 		T[akt].mx =max(T[n.son[0]].mx,T[n.son[1]].mx);
  95. 		T[akt].ans =T[n.son[0]].ans+count(n.son[1],T[n.son[0]].mx);
  96. 	}
  97.  
  98. 	pair<int,int> get(int akt, int zac, int kon, int mx_lft) {
  99. 		node n =T[akt];
  100. 		if(zac >= n.k || n.z >= kon) return make_pair(0,-1);
  101. 		if(zac == n.z && kon == n.k) return make_pair(count(akt,mx_lft),n.mx);
  102. 		pair<int,int> ret =get(n.son[0],zac,min(kon,(n.z+n.k)/2),mx_lft);
  103. 		pair<int,int> ret2 =get(n.son[1],max(zac,(n.z+n.k)/2),kon,max(mx_lft,ret.ss));
  104. 		ret.ff +=ret2.ff;
  105. 		ret.ss =max(ret.ss,ret2.ss);
  106. 		return ret;
  107. 	}
  108.  
  109. 	int get_r_bound(int akt, int l, int R) {
  110. 		// first index >= R
  111. 		node n =T[akt];
  112. 		if(n.mx < R) return n.k;
  113. 		if(n.z == n.k-1) return n.z;
  114. 		if(T[n.son[0]].k <= l) return get_r_bound(n.son[1],l,R);
  115. 		int ret =get_r_bound(n.son[0],l,R);
  116. 		if(ret < T[n.son[0]].k) return ret;
  117. 		return get_r_bound(n.son[1],l,R);
  118. 	}
  119. };
  120.  
  121. int main() {
  122. 	cin.sync_with_stdio(0);
  123. 	cin.tie(0);
  124. 	cout << fixed << setprecision(10);
  125. 	int T;
  126. 	cin >> T;
  127. 	while(T--) {
  128. 		int N,Q;
  129. 		cin >> N >> Q;
  130. 		vector<int> A(N);
  131. 		for(int i =0; i < N; i++) cin >> A[i];
  132. 		segtree I(N,A);
  133. 		for(int i =0; i < Q; i++) {
  134. 			string s;
  135. 			int id;
  136. 			cin >> s >> id;
  137. 			id--;
  138. 			if(s == "+") {
  139. 				int x;
  140. 				cin >> x;
  141. 				I.put(0,id,x);
  142. 			}
  143. 			else {
  144. 				int L,R;
  145. 				cin >> L >> R;
  146. 				int h =I.get_r_bound(0,id,R);
  147. 				cout << I.get(0,id,min(N,h+1),L-1).ff << "\n";
  148. 			}
  149. 		}
  150. 	}
  151. }
  152.  
  153. // look at my code
  154. // my code is amazing
  155.  
Runtime error #stdin #stdout #stderr 0s 15280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/36x8y0
Codechef October Challenge 2017, SHTARR
language:
C++14 (gcc 8.3)
created:
7 years 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!