fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <queue>
  4. #include <string.h>
  5. using namespace std;
  6.  
  7.  
  8.  
  9. struct E{
  10. 	long long int t,x,rx,lx;
  11. 	int lNo;
  12. 	int rNo;
  13. 	bool operator<(const E &e)const{
  14. 		return t>e.t;
  15. 	}
  16. };
  17.  
  18. struct E2{
  19. 	long long int x;
  20. 	int no;
  21. 	bool operator<(const E2 &e)const{
  22. 		return x<e.x;
  23. 	}
  24. };
  25.  
  26. struct E3{
  27. 	long long int x,d;
  28. };
  29.  
  30.  
  31. long long int ans[100003];
  32. set<E2> rs,ls,ss;
  33. set<int> nos;
  34. priority_queue<E> pq;
  35. E3 xs[100003];
  36.  
  37. void fl(E e1,long long int t){
  38. 	if(ls.size()==0)return ;
  39. 	E2 e2,eR,eL,eC;
  40. 	set<E2>::iterator itR,itL,itC;
  41. 	e2.x=e1.x;
  42. 	itL=ls.lower_bound(e2);
  43. 	if(itL==ls.end())return;
  44. 	eL=(*itL);
  45.  
  46. 	itR=rs.lower_bound(e2);
  47. 	if(itR!=rs.end()){
  48. 		eR=(*itR);
  49. 		if(eR.x<eL.x)return;
  50. 	}
  51.  
  52. 	itC=ss.upper_bound(e2);
  53. 	if(itC!=ss.end()){
  54. 		eC=(*itC);
  55. 		if(eC.x<eL.x)return;
  56. 	}
  57. 	E e3;
  58. 	e3.x=e1.x;
  59. 	e3.lNo=eL.no;
  60. 	e3.lx=eL.x;
  61. 	e3.rNo=-1;
  62. 	e3.t=abs(e1.x-eL.x);
  63. 	if(t<e3.t)return;
  64. 	pq.push(e3);
  65. }
  66.  
  67. void fr(E e1,long long int t){
  68. 	if(rs.size()==0)return ;
  69. 	E2 e2,eR,eL,eC;
  70. 	e2.x=e1.x;
  71. 	set<E2>::iterator itR,itL,itC;
  72. 	itR=rs.upper_bound(e2);
  73. 	if(itR==rs.begin())return ;
  74. 	itR--;
  75. 	eR=(*itR);
  76. 	itL=ls.lower_bound(eR);
  77. 	if(itL!=ls.end()){
  78. 		eL=(*itL);
  79. 		if(eL.x<e1.x)return;
  80. 	}
  81. 	itC=ss.lower_bound(eR);
  82. 	if(itC!=ss.end()){
  83. 		eC=(*itC);
  84. 		if(eC.x<e1.x)return ;
  85. 	}
  86. 	E e3;
  87. 	e3.x=e1.x;
  88. 	e3.rNo=eR.no;
  89. 	e3.rx=eR.x;
  90. 	e3.lNo=-1;
  91. 	e3.t=abs(e1.x-eR.x);
  92. 	//cout<<e3.t<<" "<<e3.x<<" "<<e3.rx<<" "<<e3.lx<<" "<<e3.lNo<<" "<<e3.rNo<<endl;
  93. 	if(t<e3.t)return;
  94. 	pq.push(e3);
  95. }
  96.  
  97.  
  98. void f(long long int t){
  99. 	set<E2>::iterator itL,itR;
  100. 	for(itR=rs.begin();itR!=rs.end();itR++){
  101. 		E2 xR=(*itR);
  102. 		itL=ls.upper_bound(xR);
  103. 		if(itL!=ls.end()){
  104. 			E2 xL=(*itL);
  105. 			itR++;
  106. 			//cout<<"b"<<xR.x<<" "<<" "<<xL.x<<endl;
  107. 			if(itR!=rs.end()){
  108. 				E2 xR2=(*itR);
  109. 				itR--;
  110. 				//cout<<"a"<<xR.x<<" "<<xR2.x<<" "<<xL.x<<endl;
  111. 				if(xR2.x<xL.x)continue;
  112. 			}else{
  113. 				itR--;
  114. 			}
  115. 			//
  116.  
  117. 			long long int t1=abs(xR.x-xL.x)/2;
  118. 			if(t<t1)continue;
  119. 			E e1;
  120. 			e1.rx=xR.x;
  121. 			e1.lx=xL.x;
  122. 			e1.t=t1;
  123. 			e1.x=(xL.x+xR.x)/2;
  124. 			e1.rNo=xR.no;
  125. 			e1.lNo=xL.no;
  126. 			pq.push(e1);
  127. 			//cout<<"c "<<e1.t<<" "<<e1.x<<" "<<e1.rx<<" "<<e1.lx<<" "<<e1.lNo<<" "<<e1.rNo<<endl;
  128. 		}
  129. 	}
  130. 	while(pq.size()>0){
  131. 		E e1=pq.top();
  132. 		pq.pop();
  133.  
  134. 		E2 e2;
  135. 		e2.x=e1.x;
  136. 		ss.insert(e2);
  137. 		if(e1.rNo!=-1){
  138. 			ans[e1.rNo]=e1.x;
  139. 			e2.x=e1.rx;
  140. 			rs.erase(e2);
  141. 			nos.insert(e1.rNo);
  142. 		}
  143.  
  144. 		if(e1.lNo!=-1){
  145. 			ans[e1.lNo]=e1.x;
  146. 			e2.x=e1.lx;
  147. 			ls.erase(e2);
  148. 			nos.insert(e1.lNo);
  149. 		}
  150. 		//cout<<"e "<<e1.t<<" "<<e1.x<<" "<<e1.rx<<" "<<e1.lx<<" "<<e1.lNo<<" "<<e1.rNo<<endl;
  151.  
  152. 		fr(e1,t);
  153. 		fl(e1,t);
  154. 	}
  155.  
  156. }
  157.  
  158.  
  159.  
  160. int main() {
  161. 	int n,q;
  162. 	long long int t;
  163. 	cin>>n>>t>>q;
  164. 	for(int i=0;i<n;i++){
  165. 		long long int x;
  166. 		int t1;
  167. 		cin>>x>>t1;
  168. 		E2  e2;
  169. 		e2.x=x;
  170. 		e2.no=i+1;
  171. 		xs[i+1].x=x;
  172. 		if(t1==1){
  173. 			xs[i+1].d=1;
  174. 			rs.insert(e2);
  175. 		}else{
  176. 			xs[i+1].d=-1;
  177. 			ls.insert(e2);
  178. 		}
  179. 	}
  180. 	f(t);
  181. 	for(int i=0;i<q;i++){
  182. 		int no;
  183. 		cin>>no;
  184. 		if(nos.find(no)==nos.end()){
  185. 			cout<<xs[no].x+xs[no].d*t<<endl;
  186. 		}else{
  187. 			cout<<ans[no]<<endl;
  188. 		}
  189. 	}
  190. 	return 0;
  191. }
Success #stdin #stdout 0.01s 5544KB
comments (?)
stdin
copy 
100 876 100
-10000 2
-9770 2
-9634 1
-9432 1
-8994 1
-8904 1
-8832 2
-8540 2
-8134 2
-8114 2
-7792 2
-7550 2
-7504 2
-7434 2
-7426 2
-7228 1
-7198 1
-6424 1
-6180 2
-6044 2
-5408 2
-5126 2
-5110 2
-5042 2
-5016 1
-4842 1
-4212 1
-4122 1
-3972 1
-3840 1
-3784 1
-3572 1
-3040 2
-2982 2
-2966 2
-2686 2
-2522 1
-2426 1
-2296 1
-2262 1
-2076 1
-2054 1
-2050 1
-2022 1
-1896 1
-1572 1
-1564 1
-1210 1
-716 1
-678 1
-644 1
-464 2
-198 2
354 2
396 2
482 2
540 2
668 2
712 2
764 2
864 2
1050 1
1054 2
1084 2
1320 2
1368 2
1490 2
1572 2
2356 2
2480 2
2654 2
2888 1
3454 2
3644 2
3682 2
4138 2
4468 2
4736 2
5196 2
5372 2
5694 1
5924 1
6044 2
6172 2
6250 2
6628 2
6792 2
6796 2
7310 2
7458 2
7846 2
8242 2
8260 1
8462 1
8586 1
8604 1
8740 1
8784 1
9504 1
9560 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1
2
3
4
5
6
7
stdout
copy 
-10876
-10646
-8868
-8868
-8868
-8868
-8868
-8868
-8868
-8868
-8668
-8426
-8380
-8310
-8302
-6352
-6322
-6302
-6302
-6302
-6284
-6002
-5986
-5918
-4140
-3966
-3336
-3306
-3306
-3306
-3306
-3306
-3306
-3306
-3306
-3306
-1646
-1550
-1420
-1386
-1200
-1178
-1174
-1146
-1020
-696
-688
-554
-554
-554
-554
-554
-554
-522
-480
-394
-336
-208
-164
-112
-12
1052
1052
1052
1052
1052
1052
1052
1480
1604
1778
3171
3171
3171
3171
3262
3592
3860
4320
4496
5984
5984
5984
5984
5984
5984
5984
5984
6434
6582
6970
7366
9136
9338
9462
9480
9616
9660
10380
10436
https://ideone.com/2DKwpw
language:
C++ (gcc 8.3)
created:
1 year 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!