fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef unsigned long long ull;
  8. typedef pair<ll,ll> ii;
  9. typedef vector<ll> vi;
  10. typedef vector< ii > vii;
  11.  
  12. #define INF 0x3F3F3F3F
  13. #define LINF 0x3F3F3F3F3F3F3F3FLL
  14. #define pb push_back
  15. #define mp make_pair
  16. #define pq priority_queue
  17. #define LSONE(s) ((s)&(-s)) //LASTBIT
  18. #define DEG_to_RAD(X)   (X * PI / 180)
  19. #define F first
  20. #define S second
  21. #define PI 2*acos(0)
  22.  
  23. #ifdef ONLINE_JUDGE
  24. #define debug(args...)
  25. #else
  26. #define debug(args...) fprintf(stderr,args)
  27. #endif
  28.  
  29. //////////////////////
  30. int dx[] = {1,-1,0,0};
  31. int dy[] = {0,0,-1,1};
  32. //////////////////////
  33.  
  34. const int N = 100050;
  35. const int SQ = 330;
  36.  
  37. int v[N];
  38. int n,m;
  39.  
  40. inline int scan(){
  41.     char c = getchar_unlocked();
  42.     int x = 0;
  43.     bool b=0;
  44.     while(c<'0'||c>'9'){
  45.         if(c=='-'){
  46.             b=1;
  47.         }
  48.         c=getchar_unlocked();
  49.     }
  50.     while(c>='0'&&c<='9'){
  51.         x=(x<<1)+(x<<3)+c-'0';
  52.         c=getchar_unlocked();
  53.     }
  54.     if(b){
  55.         return -x;
  56.     }
  57.     return x;
  58. }
  59.  
  60. struct est
  61. {
  62. 	int l,r,id,sq;
  63. 	est(){};
  64. 	est( int a, int b, int c )
  65. 	{
  66. 		l = a;
  67. 		r = b;
  68. 		id = c;
  69. 		sq = a/SQ;
  70. 	}
  71. 	bool operator < ( est foo ) const
  72. 	{
  73. 		if( sq != foo.sq ) return sq < foo.sq;
  74. 		return r > foo.r;
  75. 	}
  76. };
  77.  
  78. int tr[4*N];
  79.  
  80. void update( int no, int l, int r, int i, int val )
  81. {
  82. 	if( l == r )
  83. 	{
  84. 		tr[no] = val;
  85. 		return;
  86. 	}
  87. 	int nxt = (no<<1), mid = (l+r)>>1;
  88. 	if( i <= mid ) update(nxt,l,mid,i,val);
  89. 	else update(nxt+1,mid+1,r,i,val);
  90. 	tr[no] = max( tr[nxt], tr[nxt+1] );
  91. }
  92.  
  93. est que[N];
  94. int ans[N];
  95. deque<int>s[N];
  96.  
  97. void init(){
  98. 	for(int i=0;i<N;++i){
  99. 		update(1,0,N-1,i,0);
  100. 		s[i].clear();
  101. 	}
  102. }
  103.  
  104. int main()
  105. {
  106. 	//ios::sync_with_stdio(0);
  107. 	register int i,l,r;
  108. 	n = scan();
  109. 	m = scan();
  110. 	for(i=1;i<=n;++i) v[i] = scan(), v[i] += v[i-1];
  111. 	for(i=0;i<=n;++i) v[i] += 50000;
  112. 	for(i=0;i<m;++i){
  113. 		int a,b; a = scan(); b = scan(); a--;
  114. 		que[i] = est(a,b,i);
  115. 	}
  116. 	sort(que,que+m);
  117. 	int ult =- 1;
  118. 	for(i=0;i<m;++i){
  119. 		if( ult != que[i].sq ){
  120. 			init();
  121. 			l = r = que[i].l;
  122. 			s[v[r]].push_front(r);
  123. 			while( r < que[i].r ){
  124. 				r++;
  125. 				s[v[r]].push_front(r);
  126. 				int a = s[v[r]].front();
  127. 				int b = s[v[r]].back();
  128. 				update(1,0,N-1,v[r],abs(b-a));
  129. 			}
  130. 		}
  131. 		while( l < que[i].l ){
  132. 			s[v[l]].pop_back();
  133. 			if( s[v[l]].size() == 0 ) update(1,0,N-1,v[l],0);
  134. 			else{
  135. 				int a = s[v[l]].front();
  136. 				int b = s[v[l]].back();
  137. 				update(1,0,N-1,v[l],abs(b-a));
  138. 			}
  139. 			l++;
  140. 		}
  141. 		while( l > que[i].l ){
  142. 			l--;
  143. 			s[v[l]].push_back(l);
  144. 			int a = s[v[l]].front();
  145. 			int b = s[v[l]].back();
  146. 			update(1,0,N-1,v[l],abs(b-a));
  147. 		}
  148. 		while( r > que[i].r ){
  149. 			s[v[r]].pop_front();
  150. 			if( s[v[r]].size() == 0 ) update(1,0,N-1,v[r],0);
  151. 			else{
  152. 				int a = s[v[r]].front();
  153. 				int b = s[v[r]].back();
  154. 				update(1,0,N-1,v[r],abs(b-a));
  155. 			}
  156. 			r--;
  157. 		}
  158. 		ans[que[i].id] = tr[1];
  159. 		ult = que[i].sq;
  160. 	}
  161. 	for(i=0;i<m;++i) printf("%d\n",ans[i]);
  162. 	return 0;
  163. }
Time limit exceeded #stdin #stdout 5s 65920KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pHvCEH
language:
C++ (gcc 8.3)
created:
8 years 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!