fork(9) download
copy 
  1. //Mobius_Treap
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. typedef pair<int,int>   II;
  7. typedef vector< II >      VII;
  8. typedef vector<int>     VI;
  9. typedef vector< VI > 	VVI;
  10. typedef long long int 	LL;
  11.  
  12. #define PB push_back
  13. #define MP make_pair
  14. #define F first
  15. #define S second
  16. #define SZ(a) (int)(a.size())
  17. #define ALL(a) a.begin(),a.end()
  18. #define SET(a,b) memset(a,b,sizeof(a))
  19.  
  20. #define si(n) scanf("%d",&n)
  21. #define dout(n) printf("%d\n",n)
  22. #define sll(n) scanf("%lld",&n)
  23. #define lldout(n) printf("%lld\n",n)
  24. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  25.  
  26. //#define TRACE
  27.  
  28. #ifdef TRACE
  29. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  30. template <typename Arg1>
  31. void __f(const char* name, Arg1&& arg1){
  32. 	cerr << name << " : " << arg1 << std::endl;
  33. }
  34. template <typename Arg1, typename... Args>
  35. void __f(const char* names, Arg1&& arg1, Args&&... args){
  36. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  37. }
  38. #else
  39. #define trace(...)
  40. #endif
  41.  
  42. //FILE *fin = freopen("in","r",stdin);
  43. //FILE *fout = freopen("out","w",stdout);
  44.  
  45. const int N=100100;
  46. int K,A[N];
  47. pair<II,II> qu[N];
  48. deque<int> Q[N];
  49. multiset<int > my;
  50. int ans[N];
  51. bool cmp(pair<II,II> a,pair<II,II> b)
  52. {
  53. 	int aa=a.S.S;
  54. 	int bb=b.S.S;
  55. 	if(aa!=bb)
  56. 		return (aa<bb);
  57. 	return a.F.F<b.F.F;
  58. }
  59. int main()
  60. {
  61. 	int n,q;
  62. 	si(n);
  63. 	si(q);
  64. 	K=sqrt(2*N);
  65. 	A[0]=50050;
  66. 	for(int i=1;i<=n;i++)
  67. 	{
  68. 		int x;
  69. 		si(x);
  70. 		A[i]=A[i-1]+x;
  71. 		trace(i,A[i]);
  72. 	}
  73. 	for(int i=0;i<q;i++)
  74. 	{
  75. 		si(qu[i].F.F),si(qu[i].F.S);
  76. 		qu[i].F.F--;
  77. 		qu[i].S.F=i;
  78. 		qu[i].S.S=qu[i].F.S/K;
  79. 	}
  80. 	sort(qu,qu+q,cmp);
  81. 	int l=0,r=0;
  82. 	Q[A[0]].push_front(0);
  83. 	for(int i=0;i<q;i++)
  84. 	{
  85. 		int L=qu[i].F.F;
  86. 		int R=qu[i].F.S;
  87. 		while(r<R)
  88. 		{
  89. 			r++;
  90. 			if(SZ(Q[A[r]])>1)
  91. 			{
  92. 				int prev=Q[A[r]].back()-Q[A[r]].front();
  93. 				my.erase(my.find(prev));
  94. 			}
  95. 			Q[A[r]].push_back(r);
  96. 			if(SZ(Q[A[r]])>1)
  97. 			{
  98. 				int cur=Q[A[r]].back()-Q[A[r]].front();
  99. 				my.insert(cur);
  100. 			}
  101. 		}
  102. 		while(l>L)
  103. 		{
  104. 			l--;
  105. 			if(SZ(Q[A[l]])>1)
  106. 			{
  107. 				int prev=Q[A[l]].back()-Q[A[l]].front();
  108. 				my.erase(my.find(prev));
  109. 			}
  110. 			Q[A[l]].push_front(l);
  111. 			if(SZ(Q[A[l]])>1)
  112. 			{
  113. 				int cur=Q[A[l]].back()-Q[A[l]].front();
  114. 				my.insert(cur);
  115. 			}
  116. 		}
  117. 		while(l<L)
  118. 		{
  119. 			if(SZ(Q[A[l]])>1)
  120. 			{
  121. 				int prev=Q[A[l]].back()-Q[A[l]].front();
  122. 				my.erase(my.find(prev));
  123. 			}
  124. 			Q[A[l]].pop_front();
  125. 			if(SZ(Q[A[l]])>1)
  126. 			{
  127. 				int cur=Q[A[l]].back()-Q[A[l]].front();
  128. 				my.insert(cur);
  129. 			}
  130. 			l++;
  131. 		}
  132. 		while(r>R)
  133. 		{
  134. 			if(SZ(Q[A[r]])>1)
  135. 			{
  136. 				int prev=Q[A[r]].back()-Q[A[r]].front();
  137. 				my.erase(my.find(prev));
  138. 			}
  139. 			Q[A[r]].pop_back();
  140. 			if(SZ(Q[A[r]])>1)
  141. 			{
  142. 				int cur=Q[A[r]].back()-Q[A[r]].front();
  143. 				my.insert(cur);
  144. 			}
  145. 			r--;
  146. 		}
  147. 		if(!my.empty())
  148. 			ans[qu[i].S.F]=*my.rbegin();
  149. 	}
  150. 	for(int i=0;i<q;i++)
  151. 		dout(ans[i]);
  152. 	return 0;
  153. }
Success #stdin #stdout 0.08s 64376KB
comments (?)
stdin
copy 
6 4
1 1 1 -1 -1 -1
1 3
1 4
1 5
1 6
stdout
copy 
0
2
4
6
https://ideone.com/HUkmtN
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!