fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define pb push_back
  4. #define rep(i,a,b) for(int i = (a); i<(b); i++)
  5. #define ls(i) (i<<1)
  6. #define rs(i) ((i<<1)|1)
  7. #define all(x) (x).begin(), (x).end()
  8. #define sz(x) (int) (x).size()
  9. using namespace std;
  10. const int maxn = 100000;
  11. int n;
  12. int w[maxn+1],h[maxn+1];
  13. int prv[maxn+1],nxt[maxn+1];
  14. int f[maxn+1],sw[maxn+1];
  15.  
  16. class SegmentTreeMinPointUpdate
  17. {
  18. 	const static int oo = (int) 1e9+10;
  19. 	const static int maxn = (int) 1e6;
  20. 	int n;
  21. 	int l[maxn*5],r[maxn*5],it[maxn*5],vt[maxn+1];
  22.  
  23. public:
  24. 	SegmentTreeMinPointUpdate(int n = 1) { this->n = n; initIT(1,1,n); }
  25. 	void initIT(int i,int x,int y)
  26. 	{
  27. 		l[i] = x; r[i] = y; it[i] = oo; 
  28. 		if (x==y) { vt[x] = i; return; }
  29. 		int m = (x+y)>>1;
  30. 		initIT(ls(i),x,m);
  31. 		initIT(rs(i),m+1,y);
  32. 	}
  33.  
  34. 	void updatePoint(int x,int v)
  35. 	{
  36. 		it[vt[x]] = v;
  37. 		int tmp = vt[x]>>1;
  38. 		while (tmp>0) {
  39. 			it[tmp] = min(it[ls(tmp)],it[rs(tmp)]);
  40. 			tmp>>=1;
  41.  
  42. 		}
  43. 	}
  44.  
  45. 	int getIT(int i,int x,int y)
  46. 	{
  47. 		if (y<l[i] or x>r[i])
  48. 			return oo;
  49. 		if (x<=l[i] and r[i]<=y)
  50. 			return it[i];
  51. 		int res1 = getIT(ls(i),x,y), res2 = getIT(rs(i),x,y);
  52. 		return min(res1,res2);
  53. 	}
  54. };
  55.  
  56.  
  57. class SegmentTreeMaxPointUpdate
  58. {
  59. 	const static int oo = (int) 1e9+10;
  60. 	const static int maxn = (int) 1e6;
  61. 	int n;
  62. 	int l[maxn*5],r[maxn*5],it[maxn*5],vt[maxn+1];
  63.  
  64. public:
  65. 	SegmentTreeMaxPointUpdate(int n = 1) { this->n = n; initIT(1,1,n); }
  66. 	void initIT(int i,int x,int y)
  67. 	{
  68. 		l[i] = x; r[i] = y;
  69. 		if (x==y) { vt[x] = i; return; }
  70. 		int m = (x+y)>>1;
  71. 		initIT(ls(i),x,m);
  72. 		initIT(rs(i),m+1,y);
  73. 	}
  74.  
  75. 	void updatePoint(int x,int v)
  76. 	{
  77. 		it[vt[x]] = v;
  78. 		int tmp = vt[x]>>1;
  79. 		while (tmp>0) {
  80. 			it[tmp] = max(it[ls(tmp)],it[rs(tmp)]);
  81. 			tmp>>=1;
  82. 		}
  83. 	}
  84.  
  85. 	int getIT(int i,int x,int y)
  86. 	{
  87. 		if (y<l[i] or x>r[i])
  88. 			return 0;
  89. 		if (x<=l[i] and r[i]<=y)
  90. 			return it[i];
  91. 		int res1 = getIT(ls(i),x,y), res2 = getIT(rs(i),x,y);
  92. 		return max(res1,res2);
  93. 	}
  94. };
  95.  
  96. int index(vector<int>& v,int x)
  97. {
  98. 	return distance(v.begin(),lower_bound(v.begin(),v.end(),x))+1;
  99. }
  100.  
  101. const int oo = (int) 1e9+10;
  102. SegmentTreeMaxPointUpdate prvTree; 
  103. SegmentTreeMinPointUpdate nxtTree;
  104. void process()
  105. {
  106. 	vector<int> posH;
  107. 	rep(i,1,n+1) {
  108. 		posH.pb(h[i]);
  109. 		posH.pb(h[i]+1);
  110. 	}
  111. 	posH.pb(oo);
  112.  
  113. 	sort(posH.begin(),posH.end());
  114. 	posH.erase(unique(all(posH)),posH.end());
  115.  
  116. 	nxtTree.initIT(1,1,sz(posH));
  117. 	prvTree.initIT(1,1,sz(posH));
  118.  
  119. 	prvTree.updatePoint(index(posH,oo),0);
  120.  
  121. 	rep(i,1,n+1) {
  122. 		prv[i] = prvTree.getIT(1,index(posH,h[i]+1),sz(posH));
  123. 		prvTree.updatePoint(index(posH,h[i]),i);
  124. 	}
  125.  
  126. 	nxtTree.updatePoint(index(posH,oo),n+1);
  127. 	for (int i=n; i>=1; i--) {
  128. 		nxt[i] = nxtTree.getIT(1,index(posH,h[i]+1),sz(posH));
  129. 		assert(h[i] >= h[nxt[i]-1]);
  130. 		nxtTree.updatePoint(index(posH,h[i]),i);
  131. 	}
  132. }
  133.  
  134. int minPos;
  135. int dp[maxn+1];
  136. bool between(int x,int y,int z) { return min(x,z)<=y and y<=max(x,z); }
  137. int fillTo(int x,int y,int H) { 
  138. 	int res = (sw[y]-sw[x-1])*H - (f[y]-f[x-1]); 
  139. 	return res;
  140. }
  141. int caldp(int x)
  142. {
  143. 	if (dp[x]!=-1) return dp[x];
  144.  
  145. 	if (x==minPos)
  146. 		dp[x] = 0;
  147. 	if (x<minPos)
  148. 		dp[x] = fillTo(x,nxt[x]-1,h[x])+caldp(min(minPos,nxt[x]));
  149. 	if (x>minPos)
  150. 		dp[x] = fillTo(prv[x]+1,x,h[x])+caldp(max(minPos,prv[x]));
  151.  
  152. 	//cerr << "dp " << x << ' ' << dp[x] << '\n';
  153. 	return dp[x];
  154. }
  155. main()
  156. {
  157. 	ios_base::sync_with_stdio(0);
  158. 	cin >> n;
  159. 	rep(i,1,n+1) {
  160. 		cin >> w[i] >> h[i];
  161. 		f[i]=f[i-1]+w[i]*h[i];
  162. 		sw[i]=sw[i-1]+w[i];
  163. 	}
  164. 	process();
  165.  
  166. 	minPos = 1;
  167. 	rep(i,2,n+1) if (h[i] < h[minPos]) minPos = i;
  168. 	rep(i,1,n+1) assert(prv[i] < i and i < nxt[i]);
  169.  
  170. 	memset(dp,-1,sizeof(dp));
  171. 	rep(i,1,n+1) {
  172. 		if (between(prv[i],minPos,nxt[i])) {
  173. 			cout << fillTo(prv[i]+1,nxt[i]-1,h[i]+1) << '\n';
  174. 			continue;
  175. 		}
  176.  
  177. 		if (i < minPos) {
  178. 			assert(h[i] >= h[prv[i]+1]);
  179. 			assert(h[i] >= h[nxt[i]-1]); 
  180. 			cout << fillTo(prv[i]+1,nxt[i]-1,h[i]+1) + caldp(nxt[i]) << '\n';
  181. 		}
  182. 		if (i > minPos) {
  183. 			assert(h[i] >= h[prv[i]+1]);
  184. 			assert(h[i] >= h[nxt[i]-1]);
  185. 			cout << fillTo(prv[i]+1,nxt[i]-1,h[i]+1) + caldp(prv[i]) << '\n';
  186. 		}
  187. 	}
  188.  
  189. 	return 0;
  190. }
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ilUJku
language:
C++14 (gcc 8.3)
created:
5 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!