fork download 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long llo;
  5. #define mp make_pair
  6. #define pb push_back
  7. #define a first 
  8. #define b second
  9. //#define endl '\n'
  10.  
  11. #include <vector>
  12.  
  13. using namespace std;
  14. //vector<pair<llo,llo>> adj[2*500001];
  15. //llo dist[2*500001];
  16. vector<pair<int,int>> xx;
  17. /*vector<int> cc;
  18. vector<int> dd;*/
  19.  
  20. llo tree[4*500001];
  21. llo tree2[4*500001];
  22. llo tree3[4*500001];
  23. llo lazy[4*500001];
  24. llo lazy2[4*500001];
  25. //min dist,index
  26. void build(int no,int l,int r){
  27. 	////cout<<l<<"::"<<r<<"::"<<no<<endl;
  28. 	if(l==r){
  29.  
  30. 		/*if(l==0){
  31. 			//cout<<no<<endl;
  32. 		}*/
  33. 		if(xx[l].b==0){
  34. 			tree[no]=0;
  35. 		}
  36. 		else{
  37. 			tree[no]=(llo)1e15;
  38. 		}
  39. 		tree2[no]=xx[l].a;//max
  40. 		tree3[no]=xx[l].a;//min
  41. 		lazy[no]=(llo)1e15;
  42. 		lazy2[no]=(llo)1e15;
  43. 		/*if(no==2){
  44. 			//cout<<lazy[no]<<endl;
  45. 		}*/
  46. 	}
  47. 	else{
  48. 		llo mid=(l+r)/2;
  49. 		build(no*2+1,l,mid);
  50. 		build(no*2+2,mid+1,r);
  51. 		tree[no]=min(tree[no*2+1],tree[no*2+2]);
  52.  
  53. 		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
  54. 		tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
  55. 			lazy[no]=(llo)1e15;
  56. 		lazy2[no]=(llo)1e15;
  57.  
  58. 	}
  59. }
  60.  
  61. llo cd=2e14;
  62. void push(int no,int l,int r){
  63. 	//if(tree[no].a>lazy[no]+tree3[no]){}
  64. 	//if(no==2){
  65. 	//	//cout<<l<<",,"<<r<<",,"<<lazy[no]<<",,"<<lazy2[no]<<endl;
  66. 	//}
  67. 	if(lazy[no]<cd){
  68. 		tree[no]=min(tree[no],lazy[no]+tree3[no]);
  69. 		if(l<r){
  70. 			lazy[no*2+1]=min(lazy[no*2+1],lazy[no]);
  71. 			lazy[no*2+2]=min(lazy[no*2+2],lazy[no]);
  72. 		}
  73. 		lazy[no]=cd;
  74. 	}
  75. 	if(lazy2[no]<cd){
  76. 		tree[no]=min(tree[no],lazy2[no]-tree2[no]);
  77. 		if(l<r){
  78. 			lazy2[no*2+1]=min(lazy2[no*2+1],lazy2[no]);
  79. 			lazy2[no*2+2]=min(lazy2[no*2+2],lazy2[no]);
  80. 		}
  81. 		lazy2[no]=cd;
  82. 	}
  83.  
  84. }
  85.  
  86. void update(int no,int l,int r,int aa,int bb,llo cc,int stt){
  87. 	push(no,l,r);
  88. 	if(r<aa or l>bb){
  89. 		return;
  90. 	}
  91. 	if(aa<=l and r<=bb){
  92.  
  93. 		if(stt==0){
  94. 		//	//cout<<l<<",,,"<<r<<endl;
  95. 		//	//cout<<tree3[no]<<",,"<<cc<<",,"<<tree[no]<<",,"<<no<<endl;
  96.  
  97. 			tree[no]=min(tree[no],cc+tree3[no]);
  98. 		//	//cout<<tree3[no]<<",,"<<cc<<",,"<<tree[no]<<endl;
  99. 			if(l<r){
  100. 				lazy[no*2+1]=min(lazy[no*2+1],cc);
  101. 				lazy[no*2+2]=min(lazy[no*2+2],cc);
  102. 			}
  103. 		}
  104. 		else{
  105. 			//cout<<l<<"<"<<r<<",,"<<cc<<",,"<<tree2[no]<<endl;
  106. 			tree[no]=min(tree[no],cc-tree2[no]);
  107. 			if(l<r){
  108. 				lazy2[no*2+1]=min(lazy2[no*2+1],cc);
  109. 				lazy2[no*2+2]=min(lazy2[no*2+2],cc);
  110. 			}
  111. 		}
  112. 	}
  113. 	else{
  114. 		llo mid=(l+r)/2;
  115. 		update(no*2+1,l,mid,aa,bb,cc,stt);
  116. 		update(no*2+2,mid+1,r,aa,bb,cc,stt);
  117. 		tree[no]=min(tree[no*2+1],tree[no*2+2]);
  118. //		//cout<<l<<"<"<<r<<"<"<<tree[no]<<endl;
  119.  
  120. 		//tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
  121. 	//	tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
  122. 	}
  123. 	////cout<<l<<"<"<<r<<"<"<<tree[no]<<endl;
  124. }
  125. void update2(int no,int l,int r,int i){
  126. 	push(no,l,r);
  127. 	if(l==r){
  128. 	//	//cout<<l<<":::"<<r<<endl;
  129. 		tree[no]=(llo)1e17;
  130. 		tree2[no]=-(llo)1e17;
  131. 		tree3[no]=(llo)1e17;
  132. 		lazy[no]=(llo)1e17;
  133. 		lazy2[no]=(llo)1e17;
  134. 	}
  135. 	else{
  136. 		llo mid=(l+r)/2;
  137.  
  138.  
  139. 		if(i<=mid){
  140. 			update2(no*2+1,l,mid,i);
  141. 			push(no*2+2,mid+1,r);
  142. 		}
  143. 		else{
  144. 			update2(no*2+2,mid+1,r,i);
  145. 			push(no*2+1,l,mid);
  146. 		}
  147.  
  148. 		tree[no]=min(tree[no*2+1],tree[no*2+2]);
  149.  
  150.  
  151. 		tree2[no]=max(tree2[no*2+1],tree2[no*2+2]);
  152. 		tree3[no]=min(tree3[no*2+1],tree3[no*2+2]);
  153. 	}
  154. }
  155.  
  156. void brucia(int n, vector<int> &aa, vector<int> &bb, vector<llo> &tt) {
  157. 	//cc=aa;
  158. //	dd=bb;
  159.  
  160. 	for(llo i=0;i<n;i++){
  161. 		xx.pb({aa[i],i});
  162. 	}
  163. 	sort(xx.begin(),xx.end());
  164. 	build(0,0,n-1);
  165. 	////cout<<lazy[2]<<endl;
  166. 	////cout<<tree[2]<<endl;
  167. 	map<llo,llo> ind2;
  168. 	for(llo i=0;i<n;i++){
  169. 		tt[i]=-1;
  170. 		//ind2[xx[i].b]=i;
  171. 	}
  172. 	//for(auto j:xx){
  173. 		//cout<<j.a<<",,"<<j.b<<endl;
  174. 	//}
  175.  
  176. 	while(true){
  177. 		llo ac=tree[0];
  178. 		if(ac>(1e9)*n){
  179. 			break;
  180. 		}
  181. 		//cout<<ac<<endl;
  182. 		////cout<<tree[2]<<endl;
  183. 		////cout<<lazy[2]<<endl;
  184. 		int ll=0;
  185. 		int rr=n-1;
  186. 		int cur=0;
  187.  
  188. 	//	pop(0,0,n-1);
  189. 		while(ll<rr){
  190. 			int mid=(ll+rr)/2;
  191. 			push(cur*2+1,ll,mid);
  192. 			push(cur*2+2,mid+1,rr);
  193. 			if(tree[cur*2+1]==ac){
  194. 				rr=mid;
  195. 				cur*=2;
  196. 				cur+=1;
  197. 			}
  198. 			else{
  199. 				ll=mid+1;
  200. 				cur*=2;
  201. 				cur+=2;
  202. 			}
  203. 		}
  204. 		//cout<<tree[3]<<"<<"<<tree[4]<<"<<"<<tree[2]<<endl;
  205. 		//cout<<ll<<",,"<<rr<<endl;
  206. 		update2(0,0,n-1,rr);
  207. 			//cout<<tree[3]<<"<<"<<tree[4]<<"<<"<<tree[2]<<endl;
  208. 	//	//cout<<tree[2]<<endl;
  209. 		int ind=xx[rr].b;
  210. 		//cout<<tree[0]<<endl;
  211. 		tt[ind]=ac;
  212.  
  213. 		pair<int,int> kkc={min(aa[ind],bb[ind]),0};
  214. 		int l=lower_bound(xx.begin(),xx.end(),kkc)-xx.begin();
  215. 		kkc={max(aa[ind],bb[ind])+1,0};
  216. 		int r=lower_bound(xx.begin(),xx.end(),kkc)-xx.begin()-1;;
  217. 		if(aa[ind]<bb[ind]){
  218. 			//stt=0;
  219. 			update(0,0,n-1,l,r,ac-aa[ind],0);
  220. 		}
  221. 		else{
  222. 			update(0,0,n-1,l,r,ac+aa[ind],1);
  223. 		}
  224. 		//cout<<endl<<endl;
  225. 	}
  226.  
  227.  
  228. }
  229.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/YdLRaN
8
18 14
5 12
13 22
21 10
8 9
19 12
21 19
15 20
language:
C++14 (gcc 8.3)
created:
3 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!