fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <string>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <cassert>
  9. #include <ctime>
  10. #include <queue>
  11. #include <map>
  12. #include <list>
  13. #include <fstream>
  14. #include <iomanip>
  15. #include <set>
  16.  
  17. #define For(i,a,b) for(int (i)=(a);(i)<=int(b);(i)++)
  18. #define Ford(i,a,b) for(int (i)=(a);(i)>=int(b);(i)--)
  19. #define Rep(i,a,b) for(int (i)=(a);(i)<int(b);(i)++)
  20. #define type(x) __typeof((x).begin())
  21. #define foreach(it,x) for(type(x) it = (x).begin() ; it!=(x).end() ; it++ )
  22. #define fi first
  23. #define se second
  24. #define dbg(x) cerr<<#x<<":"<<x<<endl
  25. #define dg(x) cerr<<#x<<":"<<x<<' '
  26. #define fill(x,y) memset(x,y,sizeof x)
  27. #define all(x) x.begin(),x.end()
  28. #define bin(x) (1LL<<(x))
  29. #define gcd __gcd
  30. #define pb push_back  
  31. #define mp make_pair 
  32.  
  33. using namespace std;
  34.  
  35. typedef long long Lint;
  36. typedef pair<int,int> ii;
  37. typedef pair<Lint,Lint> Lii;
  38. typedef pair<ii,ii> iii;
  39.  
  40. const int inf = 1e9+5;
  41. const Lint Linf = 1e18+5;
  42.  
  43. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  44. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  45. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  46. template<class T> inline T lcm(T a,T b){
  47.     return a/gcd(a,b)*b;
  48. }
  49.  
  50. int read(){
  51. int res = 0 ;
  52. int neg ;
  53. while(true){
  54. char ch = getchar();
  55. if((ch>='0' && ch<='9') || ch=='-'){
  56. if(ch=='-') neg = -1;
  57. else neg = 1 , res = ch-'0';
  58. break;
  59. }
  60. }
  61. while(true){
  62. char ch = getchar();
  63. if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';
  64. else break;
  65. }
  66. return res*neg;
  67. }
  68. void print(int x){
  69.  
  70. if(x==0){
  71. putchar('0');
  72. putchar('\n');
  73. return ;
  74. }
  75. static char buf[20];
  76. int nn = 0 ;
  77. if(x<0) putchar('-') , x*=-1;
  78. while(x){
  79. buf[++nn] = x%10+'0';
  80. x/=10;
  81. }
  82. Ford(i,nn,1) putchar(buf[i]);
  83. putchar('\n');
  84. }
  85.  
  86. const int MAXN = 1e5+5;
  87.  
  88. set<int> s;
  89. int used[MAXN];
  90.  
  91. int lazy[MAXN*5];
  92.  
  93. inline void push_down(int k){
  94. 	if(lazy[k]!=-1){
  95. 		umax(lazy[k+k],lazy[k]);
  96. 		umax(lazy[k+k+1],lazy[k]);
  97. 		lazy[k] = -1; 
  98. 	}
  99. }
  100.  
  101. void upd(int k,int b,int e,int x1,int x2,int val){
  102. 	if(b>x2 || e<x1) return ;
  103. 	if(b>=x1 && e<=x2){
  104. 		umax(lazy[k],val);
  105. 		return ;
  106. 	}
  107. 	push_down(k);
  108. 	upd(k*2,b,(b+e)/2,x1,x2,val);
  109. 	upd(k*2+1,(b+e)/2+1,e,x1,x2,val);
  110. }
  111.  
  112. int find(int k,int b,int e,int x){
  113. 	if(b>x || e<x) return 0;
  114. 	if(b==e) return lazy[k];
  115. 	push_down(k);
  116. 	int L = find(k*2,b,(b+e)/2,x);
  117. 	int R = find(k*2+1,(b+e)/2+1,e,x);
  118. 	return L+R;
  119. }
  120.  
  121. void DBG(){
  122. 	foreach(it,s)
  123. 		printf("%d ",*it);
  124. 	puts("");	
  125. }
  126.  
  127. int main(){
  128.  
  129. 	int N = read();
  130. 	int M = read();
  131. 	int Q = read();
  132.  
  133. 	s.insert(0);
  134. 	Rep(i,1,N){
  135. 		s.insert(i);
  136. 		int u = read();
  137. 		int v = read();
  138. 		assert(u+1==v);
  139. 		assert(u==i);
  140. 	}
  141.  
  142. 	s.insert(N);
  143.  
  144. 	For(i,1,M){
  145. 		int v = read();
  146. 		if(!used[v]){
  147. 			type(s) left = s.lower_bound(v);
  148. 			left--;
  149. 			type(s) right = s.upper_bound(v);
  150. 			int L = *left ; 
  151. 			int R = *right;
  152. 			upd(1,1,N,L+1,R,R-L);
  153. 			s.erase(s.find(v));
  154. 		}else{
  155. 			s.insert(v);
  156. 		}
  157. 		used[v]^=1; 
  158. 	}
  159.  
  160. 	while(Q--){
  161. 		int u = read();
  162. 		print(max(1,find(1,1,N,u))) ;
  163. 	}
  164.  
  165. 	return 0;
  166. }
  167.  
Time limit exceeded #stdin #stdout 5s 5244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i9qnBA
language:
C++ (gcc 8.3)
created:
11 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!