fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 2e6;
  11. const int inf = 1e9;
  12.  
  13. pir a[maxn];
  14. int Max[maxn],Min[maxn],val[maxn],par[maxn],V[maxn],dq[maxn];
  15.  
  16. inline int findp(int x){
  17. 	return (x == par[x]) ? x : par[x] = findp(par[x]);
  18. }
  19. inline void add(int u,int v){
  20. 	int x = findp(u),y = findp(v);
  21. 	if (x != y){
  22. 		par[y] = x;
  23. 		V[x] = min(V[x],V[y]);
  24. 	}
  25. }
  26.  
  27. vector<pir> tcon[maxn],tcha[maxn],tmin[maxn],tmax[maxn];
  28.  
  29. inline void prepare(int n){
  30. 	int M = a[1].se,m = a[1].se;
  31. 	for (int i = 1 ; i <= n ; i++){
  32. 		M = max(M,a[i].se);
  33. 		m = min(m,a[i].se);
  34.  
  35. 		Max[i] = M;
  36. 		Min[i] = m;
  37. 	}
  38.  
  39.     M = a[n].se,m = a[n].se;
  40. 	int pmax = 1,pmin = 1;
  41.  
  42.     for (int i = n - 1 ; i > 1 ; i--){
  43.     	M = max(M,a[i + 1].se),m = min(m,a[i + 1].se);
  44.  
  45.     	pmax = max(pmax,1);
  46.     	pmin = max(pmin,1);
  47.  
  48.     	while (pmax <= i && Max[pmax] <= M) pmax++;
  49.     	while (pmin <= i && Min[pmin] >= m) pmin++;
  50.  
  51.     	tcon[min(i,min(pmax,pmin))].push_back({1,a[i].fi + M - m});
  52.  
  53.     	//tcha 
  54.     	if (max(pmax,pmin) + 1 <= i)
  55.     	   tcha[i].push_back({max(pmax,pmin) + 1,a[i].fi});
  56.  
  57.     	if (pmax < pmin && pmax < i)
  58.     	   tmin[min(i,pmin)].push_back({pmax + 1,a[i].fi - m});
  59.  
  60.     	if (pmin < pmax && pmin < i)
  61.     	   tmax[min(i,pmax)].push_back({pmin + 1,a[i].fi + M});
  62. 	}
  63. }
  64.  
  65. int solve_con(int n){
  66. 	int res = inf;
  67.     for (int i = 1 ; i <= n ; i++)
  68.       val[i] = -a[i].fi;
  69.  
  70. 	int m = 0;
  71.  
  72. 	for (int i = 1 ; i <= n ; i++){
  73. 		par[i] = i;
  74. 		V[i] = val[i];
  75.  
  76. 		while (m > 0 && val[dq[m]] >= val[i]){
  77. 			add(dq[m],i);
  78. 			m--;
  79. 		}
  80. 		dq[++m] = i;
  81.  
  82. 		for (pir x : tcon[i])
  83. 			res = min(res,V[findp(x.fi)]+ x.se);
  84. 	}
  85.  
  86. 	return res;
  87. }
  88. int solve_cha(int n){
  89. 	int res = inf;
  90.     for (int i = 1 ; i <= n ; i++)
  91.       val[i] = Max[i - 1] - Min[i -1 ] - a[i].fi;
  92.  
  93. 	int m = 0;
  94.  
  95. 	for (int i = 1 ; i <= n ; i++){
  96. 		par[i] = i;
  97. 		V[i] = val[i];
  98.  
  99. 		while (m > 0 && val[dq[m]] >= val[i]){
  100. 			add(dq[m],i);
  101. 			m--;
  102. 		}
  103. 		dq[++m] = i;
  104.  
  105. 		for (pir x : tcha[i])
  106. 			res = min(res,V[findp(x.fi)] + x.se);
  107. 	}
  108.  
  109. 	return res;
  110. }
  111.  
  112. int solve_tmin(int n){
  113. 	int res = inf;
  114.     for (int i = 1 ; i <= n ; i++)
  115.       val[i] = Max[i - 1] - a[i].fi;
  116.  
  117. 	int m = 0;
  118.  
  119. 	for (int i = 1 ; i <= n ; i++){
  120. 		par[i] = i;
  121. 		V[i] = val[i];
  122.  
  123. 		while (m > 0 && val[dq[m]] >= val[i]){
  124. 			add(dq[m],i);
  125. 			m--;
  126. 		}
  127. 		dq[++m] = i;
  128.  
  129. 		for (pir x : tmin[i])
  130. 			res = min(res,V[findp(x.fi)]+ x.se);
  131. 	}
  132.  
  133. 	return res;
  134. }
  135. int solve_tmax(int n){
  136. 	int res = inf;
  137.     for (int i = 1 ; i <= n ; i++)
  138.       val[i] = -Min[i - 1] - a[i].fi;
  139.  
  140. 	int m = 0;
  141.  
  142. 	for (int i = 1 ; i <= n ; i++){
  143. 		par[i] = i;
  144. 		V[i] = val[i];
  145.  
  146. 		while (m > 0 && val[dq[m]] >= val[i]){
  147. 			add(dq[m],i);
  148. 			m--;
  149. 		}
  150. 		dq[++m] = i;
  151.  
  152. 		for (pir x : tmax[i])
  153. 			res = min(res,V[findp(x.fi)] + x.se);
  154. 	}
  155.  
  156. 	return res;
  157. }
  158.  
  159. int solve_prefix(int n){
  160. 	int M = 0,m = inf,res = inf;
  161.  
  162. 	for (int i = n - 1 ; i > 0 ; i--){
  163. 		M = max(M,a[i + 1].se);
  164. 		m = min(m,a[i + 1].se);
  165.  
  166. 		res = min(res,a[i].fi - a[1].fi + M - m);
  167. 	}
  168.  
  169. 	M = 0,m = inf;
  170. 	for (int i = 2 ; i <= n ; i++){
  171. 		M = max(M,a[i - 1].se);
  172. 		m = min(m,a[i - 1].se);
  173. 		res = min(res,a[n].fi - a[i].fi + M - m);
  174. 	}
  175. 	return res;
  176. }
  177.  
  178. int solve(int n){
  179. 	//TH1 : only 
  180. 	int res = INT_MAX;
  181.  
  182. 	res = min(res,solve_con(n));
  183. 	res = min(res,solve_cha(n));
  184. 	res = min(res,solve_tmin(n));
  185. 	res = min(res,solve_tmax(n));
  186. 	res = min(res,solve_prefix(n));
  187.  
  188. 	return res;
  189. }
  190.  
  191. int main(){
  192. 	ios_base::sync_with_stdio(false);
  193. 	cin.tie(0);cout.tie(0);
  194.  
  195. //	freopen("TDIV.inp","r",stdin);
  196. //	freopen("TDIV.out","w",stdout);
  197.  
  198. 	int n;
  199. 	cin >> n;
  200. 	for (int i = 1 ; i <= n ; i++) cin >> a[i].fi >> a[i].se;
  201.  
  202. 	prepare(n);
  203. 	cout << solve(n) << "\n";
  204. 	return 0;
  205. }
  206.  
Success #stdin #stdout 0.05s 204908KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/8tDKVs
language:
C++14 (gcc 8.3)
created:
6 days 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!