fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <string>
  5. #include <map>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <bitset>
  11. #include <climits>
  12. #include <string.h>
  13. #include <stdlib.h>
  14. #include <time.h>
  15.  
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19. typedef long double ld;
  20.  
  21. #define pb(a) push_back(a)
  22.  
  23. int N = 1e5 + 1;
  24. int mod = 998244353;
  25. const ll inf = LLONG_MAX;
  26.  
  27. int mult(int a, int b)
  28. {
  29. 	return a * 1LL * b % mod;
  30. }
  31.  
  32. int sum(int a, int b)
  33. {
  34. 	return ((a % mod) + (b % mod)) % mod;
  35. }
  36.  
  37. int mus(int a, int b)
  38. {
  39. 	return (((a % mod) - (b % mod)) + mod) % mod;
  40. }
  41.  
  42. int binpow(int a, int n)
  43. {
  44. 	if (n == 0)
  45. 		return 1;
  46. 	if (n % 2 == 1)
  47. 		return binpow(a, n - 1) * 1LL * a % mod;
  48. 	else
  49. 	{
  50. 		int b = binpow(a, n / 2);
  51. 		return b * 1LL * b % mod;
  52. 	}
  53. }
  54.  
  55. ll gcd(ll a, ll b)
  56. {
  57. 	if (a == 0)
  58. 		return b;
  59. 	if (b == 0)
  60. 		return a;
  61. 	if (a > b)
  62. 		return gcd(a % b, b);
  63. 	return gcd(a, b % a);
  64. }
  65.  
  66. struct segtreex{
  67. 	int NO_OP = -1;
  68.  
  69. 	struct node{
  70. 		int set;
  71. 		int mx;
  72. 	};
  73.  
  74. 	vector<node> t;
  75. 	int size;
  76. 	void init(int n){
  77. 		size = 1;
  78. 		while(size < n){
  79. 			size *= 2;
  80. 		}
  81. 		t.assign(2 * size - 1, {NO_OP, 0});
  82. 		for(int i = size - 1; i < 2 * size - 1; i++){
  83. 			t[i].set = 0;
  84. 		}
  85. 	}
  86.  
  87. 	void push(int x){
  88. 		if(t[x].set == NO_OP)
  89. 			return;
  90. 		t[2 * x + 1].mx = t[x].set;
  91. 		t[2 * x + 2].mx = t[x].set;
  92. 		t[2 * x + 1].set = t[x].set;
  93. 		t[2 * x + 2].set = t[x].set;
  94. 		t[x].set = NO_OP;
  95. 	}
  96.  
  97. 	void modify(int l, int r, int v, int x, int lx, int rx){
  98. 		if(l >= rx || lx >= r)
  99. 			return;
  100. 		if(l <= lx && rx <= r){
  101. 			t[x].set = v;
  102. 			t[x].mx = v;
  103. 			return;
  104. 		}
  105. 		push(x);
  106. 		int m = (lx + rx) / 2;
  107. 		modify(l, r, v, 2 * x + 1, lx, m);
  108. 		modify(l, r, v, 2 * x + 2, m, rx);
  109. 		t[x].mx = max(t[2 * x + 1].mx, t[2 * x + 2].mx);
  110. 	}
  111.  
  112. 	void modify(int l, int r, int v){
  113. 		modify(l, r, v, 0, 0, size);
  114. 	}
  115.  
  116. 	int getmax(int l, int r, int x, int lx, int rx){
  117. 		if(l >= rx || r <= lx)
  118. 			return -1;
  119. 		if(l <= lx && rx <= r){
  120. 			return t[x].mx;
  121. 		}
  122. 		push(x);
  123. 		int m = (lx + rx) / 2;
  124. 		int mxl = getmax(l, r, 2 * x + 1, lx, m);
  125. 		int mxr = getmax(l, r, 2 * x + 2, m, rx);
  126. 		return max(mxl, mxr);
  127. 	}
  128.  
  129. 	int getmax(int l, int r){
  130. 		return getmax(l, r, 0, 0, size);
  131. 	}
  132. };
  133.  
  134. struct segtreey{
  135. 	unordered_map<ll, ll> t;
  136. 	ll size;
  137.  
  138. 	void init(ll n){
  139. 		size = 1;
  140. 		while(size < n)
  141. 			size *= 2;
  142. 	}
  143.  
  144. 	void add(ll l, ll r, ll x, ll lx, ll rx, ll v){
  145. 		if(l >= rx || lx >= r){
  146. 			return;
  147. 		}
  148. 		if(l <= lx && rx <= r){
  149. 			t[x] += v;
  150. 			return;
  151. 		}
  152. 		ll m = (lx + rx) / 2;
  153. 		add(l, r, 2 * x + 1, lx, m, v);
  154. 		add(l, r, 2 * x + 2, m, rx, v);
  155. 	}
  156.  
  157. 	void add(ll l, ll r, ll v){
  158. 		add(l, r, 0, 0, size, v);
  159. 	}
  160.  
  161. 	ll gety(ll i, ll x, ll lx, ll rx){
  162. 		if(lx + 1 == rx){
  163. 			return t[x];
  164. 		}
  165. 		ll m = (lx + rx) / 2;
  166. 		if(i < m)
  167. 			return gety(i, 2 * x + 1, lx, m) + t[x];
  168. 		else
  169. 			return gety(i, 2 * x + 2, m, rx) + t[x];
  170. 	}
  171.  
  172. 	ll gety(ll i){
  173. 		return gety(i, 0, 0, size);
  174. 	}
  175. };
  176.  
  177. int main()
  178. {
  179. 	ios_base::sync_with_stdio(false);
  180. 	cin.tie(0);
  181. 	int n, q;
  182. 	cin >> n >> q;
  183. 	segtreex tx;
  184. 	segtreey ty;
  185. 	tx.init(n);
  186. 	ty.init(1e11);
  187. 	while(q--){
  188. 		int t;
  189. 		cin >> t;
  190. 		if(t == 1){
  191. 			int l, r, h;
  192. 			cin >> l >> r >> h;
  193. 			int top = tx.getmax(l - 1, r);
  194. 			tx.modify(l - 1, r, top + h);
  195. 			ty.add(top + 1, top + h + 1, r - l + 1);
  196. 		}else{
  197. 			int y;
  198. 			cin >> y;
  199. 			cout << ty.gety(y) << '\n';
  200. 		}
  201. 	}
  202. }		
  203.  
  204.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:135:2: error: ‘unordered_map’ does not name a type
  unordered_map<ll, ll> t;
  ^~~~~~~~~~~~~
prog.cpp: In member function ‘void segtreey::add(ll, ll, ll, ll, ll, ll)’:
prog.cpp:149:4: error: ‘t’ was not declared in this scope
    t[x] += v;
    ^
prog.cpp: In member function ‘ll segtreey::gety(ll, ll, ll, ll)’:
prog.cpp:163:11: error: ‘t’ was not declared in this scope
    return t[x];
           ^
prog.cpp:167:39: error: ‘t’ was not declared in this scope
    return gety(i, 2 * x + 1, lx, m) + t[x];
                                       ^
prog.cpp:169:39: error: ‘t’ was not declared in this scope
    return gety(i, 2 * x + 2, m, rx) + t[x];
                                       ^
stdout
copy 
Standard output is empty
https://ideone.com/iwQPaQ
language:
C++ (gcc 8.3)
created:
2 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!