fork(20) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<ll> vi;
  18. typedef long double ld; 
  19. typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20.  
  21. ll a[233333];
  22. const ll INF = ll(1e18);
  23. vector<ii> pty[222222];
  24. vector<ii> ptx[222222];
  25. vector<ll> Y[222222];
  26.  
  27. struct DSU
  28. {
  29. 	ll S;
  30.  
  31. 	struct node
  32. 	{
  33. 		ll p; 
  34. 		ll l,r;
  35. 	};
  36. 	vector<node> dsu;
  37.  
  38. 	DSU(ll n)
  39. 	{
  40. 		S = n;
  41. 		for(ll i = 0; i < n; i++)
  42. 		{
  43. 			node tmp;
  44. 			tmp.p = i; 
  45. 			tmp.l=tmp.r=i;
  46. 			dsu.pb(tmp);
  47. 		}
  48. 	}
  49.  
  50. 	void reset(ll n)
  51. 	{
  52. 		dsu.clear();
  53. 		S = n;
  54. 		for(ll i = 0; i < n; i++)
  55. 		{
  56. 			node tmp;
  57. 			tmp.p = i;
  58. 			tmp.l=tmp.r=i;
  59. 			dsu.pb(tmp);
  60. 		}
  61. 	}
  62.  
  63. 	ll rt(ll u)
  64. 	{
  65. 		if(dsu[u].p == u) return u;
  66. 		dsu[u].p = rt(dsu[u].p);
  67. 		return dsu[u].p;
  68. 	}
  69.  
  70. 	void merge(ll u, ll v)
  71. 	{
  72. 		u = rt(u); v = rt(v);
  73. 		if(u == v) return ;
  74. 		if(rand()&1) swap(u, v);
  75. 		dsu[v].p = u;
  76. 		dsu[u].l = min(dsu[u].l,dsu[v].l);
  77. 		dsu[u].r = max(dsu[u].r,dsu[v].r);
  78. 	}
  79.  
  80. 	bool sameset(ll u, ll v)
  81. 	{
  82. 		if(rt(u) == rt(v)) return true;
  83. 		return false;
  84. 	}
  85. };
  86.  
  87.  
  88. class LazySegmentTree {
  89. private:
  90. 	int size_;
  91. 	vector<long long> v, lazy;
  92. 	void update(int a, int b, long long x, int k, int l, int r) {
  93. 		push(k, l, r);
  94. 		if (r <= a || b <= l) return;
  95. 		if (a <= l && r <= b) {
  96. 			lazy[k] += x;
  97. 			push(k, l, r);
  98. 		}
  99. 		else {
  100. 			update(a, b, x, k * 2, l, (l + r) >> 1);
  101. 			update(a, b, x, k * 2 + 1, (l + r) >> 1, r);
  102. 			v[k] = merge(v[k * 2], v[k * 2 + 1]);
  103. 		}
  104. 	}
  105. 	long long query(int a, int b, int k, int l, int r) {
  106. 		push(k, l, r);
  107. 		if (r <= a || b <= l) return 0;
  108. 		if (a <= l && r <= b) return v[k];
  109. 		long long lc = query(a, b, k * 2, l, (l + r) >> 1);
  110. 		long long rc = query(a, b, k * 2 + 1, (l + r) >> 1, r);
  111. 		return merge(lc, rc);
  112. 	}
  113.  
  114. public:
  115. 	LazySegmentTree() : v(vector<long long>()), lazy(vector<long long>()) {};
  116. 	LazySegmentTree(int n) {
  117. 		for (size_ = 1; size_ < n;) size_ <<= 1;
  118. 		v.resize(size_ * 2);
  119. 		lazy.resize(size_ * 2);
  120. 	}
  121. 	inline void push(int k, int l, int r) {
  122. 		if (lazy[k] != 0) {
  123. 			v[k] += lazy[k];
  124. 			if (r - l > 1) {
  125. 				lazy[k * 2] += lazy[k];
  126. 				lazy[k * 2 + 1] += lazy[k];
  127. 			}
  128. 			lazy[k] = 0;
  129. 		}
  130. 	}
  131. 	inline long long merge(long long x, long long y) {
  132. 		return max(x,y);
  133. 	}
  134. 	inline void update(int l, int r, long long x) {
  135. 		update(l, r, x, 1, 0, size_);
  136. 	}
  137. 	inline long long query(int l, int r) {
  138. 		return query(l, r, 1, 0, size_);
  139. 	}
  140. };
  141.  
  142. ll active[222222];
  143. int main()
  144. {
  145. 	ios_base::sync_with_stdio(0); cin.tie(0);
  146. 	ll n; cin>>n;
  147. 	for(ll i=0;i<n;i++)
  148. 	{
  149. 		cin>>a[i];
  150. 		a[i]=n-a[i]-1;
  151. 		if(a[i]>=0) Y[a[i]].pb(i);
  152. 	}
  153. 	ll q; cin>>q;
  154. 	ll ans = 0;
  155. 	for(ll i=0;i<q;i++)
  156. 	{
  157. 		ll x,y; cin>>x>>y; x--;  
  158. 		ll v;cin>>v;
  159. 		ptx[x].pb({n-y,v});
  160. 		ans+=v;
  161. 	}
  162. 	for(ll i=0;i<n;i++)
  163. 	{
  164. 		sort(ptx[i].rbegin(),ptx[i].rend());
  165. 		vector<ii> S;
  166. 		for(ii z:ptx[i])
  167. 		{
  168. 			if(!S.empty()&&z.se<=S.back().se) continue;
  169. 			S.pb(z);
  170. 		}
  171. 		ll las=0;
  172. 		for(ii x:S)
  173. 		{
  174. 			pty[x.fi].pb({i,x.se-las});
  175. 			las=x.se;
  176. 		}
  177. 	}
  178. 	DSU dsu(n);
  179. 	LazySegmentTree st(n);
  180. 	for(ll i=n-1;i>=0;i--)
  181. 	{
  182. 		//merge
  183. 		for(ll x:Y[i])
  184. 		{
  185. 			ll ans=0;
  186. 			ll resl=0;
  187. 			ll resr=0;
  188. 			if(x-1>=0&&active[x-1])
  189. 			{
  190. 				ll rt = dsu.rt(x-1);
  191. 				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
  192. 				resl=st.query(l,r+1);
  193. 				ans+=resl;
  194. 			}
  195. 			if(x+1<n&&active[x+1])
  196. 			{
  197. 				ll rt = dsu.rt(x+1);
  198. 				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
  199. 				resr=st.query(l,r+1);
  200. 				ans+=resr;
  201. 			}
  202. 			if(x-1>=0&&active[x-1])
  203. 			{
  204. 				ll rt = dsu.rt(x-1);
  205. 				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
  206. 				st.update(l,r+1,resr);
  207. 			}
  208. 			if(x+1<n&&active[x+1])
  209. 			{
  210. 				ll rt = dsu.rt(x+1);
  211. 				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
  212. 				st.update(l,r+1,resl);
  213. 			}
  214. 			if(x-1>=0&&active[x-1]) dsu.merge(x-1,x);
  215. 			if(x+1<n&&active[x+1]) dsu.merge(x,x+1);
  216. 			active[x]=1;
  217. 			st.update(x,x+1,ans);
  218. 		}
  219. 		//extend
  220. 		for(ii pt:pty[i])
  221. 		{
  222. 			ll x=pt.fi; ll v = pt.se;
  223. 			st.update(x,x+1,v);
  224. 		}
  225. 	}
  226. 	ll mx=0; ll sum=0;
  227. 	for(ll i=0;i<n;i++)
  228. 	{
  229. 		if(a[i]<0)
  230. 		{
  231. 			sum+=mx;
  232. 			mx=0; continue;
  233. 		}
  234. 		mx=max(mx,st.query(i,i+1));
  235. 	}
  236. 	sum+=mx;
  237. 	ans-=sum;
  238. 	cout<<ans<<'\n';
  239. }
  240.  
Runtime error #stdin #stdout 0s 18776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hvzTbJ
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!