fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include "shortcut.h"
  3. #define ff first
  4. #define ss second
  5. using namespace std;
  6.  
  7. long long find_shortcut(int N, vector<int> l, vector<int> d, int C) {
  8. 	vector<long long> max_lft0(N,0),max_rt0(N,0),max_lft(N,0),max_rt(N,0),pos(N,0);
  9. 	long long x =d[0], minD =0;
  10. 	for(int i =0; i < N; i++) minD =max(minD,d[i]-1LL);
  11. 	max_lft0[0] =max_lft[0] =d[0];
  12. 	for(int i =1; i < N; i++) {
  13. 		pos[i] =pos[i-1]+l[i-1];
  14. 		max_lft0[i] =max(pos[i]+x,1LL*d[i]);
  15. 		max_lft[i] =max(max_lft[i-1],pos[i]+d[i]+x);
  16. 		x =max(x,d[i]-pos[i]);}
  17. 	minD =max(minD,min(1LL*C,pos[N-1])-1LL);
  18. 	x =d[N-1]+pos[N-1];
  19. 	max_rt0[N-1] =max_rt[N-1] =d[N-1];
  20. 	for(int i =N-2; i >= 0; i--) {
  21. 		max_rt0[i] =max(-pos[i]+x,1LL*d[i]);
  22. 		max_rt[i] =max(max_rt[i+1],-pos[i]+d[i]+x);
  23. 		x =max(x,d[i]+pos[i]);}
  24.  
  25. 	srand(pos[N-1]+pos[N/2]);
  26. 	for(int i =0; i < N; i++) minD =max(minD,min(pos[i],pos[N-1]-pos[i])-1);
  27.  
  28. 	vector<long long> posmd_suf(N), pospd_pref(N);
  29. 	for(int i =0; i < N; i++) posmd_suf[i] =pos[i]-d[i], pospd_pref[i] =pos[i]+d[i];
  30. 	for(int i =1; i < N; i++) pospd_pref[i] =max(pospd_pref[i],pospd_pref[i-1]);
  31. 	for(int i =N-2; i >= 0; i--) posmd_suf[i] =min(posmd_suf[i],posmd_suf[i+1]);
  32.  
  33. 	long long maxD =max_lft[N-1];
  34. 	vector< pair<long long,int> > st;
  35. 	while(maxD-minD > 1) {
  36. 		long long D =(minD+maxD)/2;
  37. 		long long mindif =-D+C+max_lft[N-1], maxdif =1e18, minsum =-1e18, maxsum =1e18;
  38. /*
  39. 		pos[up]+d[up] > D+(pos[low]-d[low])
  40. 		minsum == -D+C + max (pos[up]+d[up])+(pos[low]+d[low])
  41. 		maxsum == D-C + min (pos[up]-d[up])+(pos[low]-d[low])
  42. 		mindif == -D+C + max_lft[N-1]
  43. 		maxdif == D-C + min (pos[up]-d[up])-(pos[low]+d[low])
  44. */
  45.  
  46. 		long long realD =0;
  47.  
  48. 		int a =-1;
  49. 		x =1e18;
  50. 		st.clear();
  51. 		if(mindif > pos[N-1]) {minD =D; continue;}
  52. 		for(int i =N-1; i >= 0; i--) {
  53. 			x =D+pos[i]-d[i];
  54. 			while(a < (int)st.size()-1 && st[a+1].ff > x) a++;
  55. 			if(a >= 0) {
  56. 				maxsum =min(maxsum,D-C+pos[i]-d[i]+posmd_suf[st[a].ss]);
  57. 				maxdif =min(maxdif,D-C-pos[i]-d[i]+posmd_suf[st[a].ss]);
  58. 				}
  59. 			if(a < (int)st.size()-1) realD =max(realD,st[a+1].ff-pos[i]+d[i]);
  60. 			if(maxdif < max(0LL,mindif) || maxsum < 0) break;
  61. 			while(!st.empty() && st.back().ff <= pos[i]+d[i]) st.pop_back();
  62. 			a =min(a,(int)st.size()-1);
  63. 			st.push_back(make_pair(pos[i]+d[i],i));
  64. 			}
  65. 		if(maxdif < mindif || maxsum < 0) {minD =D; continue;}
  66. 		a =-1;
  67. 		x =-1e18;
  68. 		st.clear();
  69. 		for(int i =0; i < N; i++) {
  70. 			x =pos[i]+d[i]-D;
  71. 			while(a < (int)st.size()-1 && st[a+1].ff < x) a++;
  72. 			if(a >= 0) 
  73. 				minsum =max(minsum,-D+C+pos[i]+d[i]+pospd_pref[st[a].ss]);
  74. 			while(!st.empty() && st.back().ff >= pos[i]-d[i]) st.pop_back();
  75. 			a =min(a,(int)st.size()-1);
  76. 			st.push_back(make_pair(pos[i]-d[i],i));
  77. 			}
  78. 		if(maxsum < minsum) {minD =D; continue;}
  79.  
  80. 		bool ok =false;
  81. 		int sumlft =N-1, sumrt =N-1, diflft =0, difrt =0;
  82. 		for(int i =0; i < N; i++) {
  83. 			while(diflft < N && pos[diflft] < pos[i]+mindif) diflft++;
  84. 			while(difrt < N && pos[difrt] <= pos[i]+maxdif) difrt++;
  85. 			while(sumrt >= 0 && pos[sumrt]+pos[i] > maxsum) sumrt--;
  86. 			while(sumlft >= 0 && pos[sumlft]+pos[i] >= minsum) sumlft--;
  87. 			if(diflft == N || sumrt < 0) break;
  88. 			int lft =max(i,max(diflft,sumlft+1)), rt =min(difrt-1,sumrt);
  89. 			if(lft <= rt) {
  90. 				realD =max(realD,D+(pos[(lft+rt)/2]+pos[i])-maxsum);
  91. 				realD =max(realD,D-(pos[(lft+rt)/2]+pos[i])+minsum);
  92. 				realD =max(realD,D-(pos[(lft+rt)/2]-pos[i])+mindif);
  93. 				realD =max(realD,D+(pos[(lft+rt)/2]-pos[i])-maxdif);
  94. 				D =realD;
  95. 				ok =true;
  96. 				break;}
  97. 			}
  98.  
  99. 		if(!ok) minD =D;
  100. 		else maxD =D;}
  101.  
  102.     return maxD;}
  103.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:2:22: fatal error: shortcut.h: No such file or directory
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/ypN9Um
IOI 2016 shortcut
language:
C++14 (gcc 8.3)
created:
8 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!