fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define SZ(X) ((int)(X).size())
  3. #define ALL(X) (X).begin(), (X).end()
  4. #define REP(I, N) for (int I = 0; I < (N); ++I)
  5. #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
  6. #define RREP(I, N) for (int I= (N)-1; I>=0; --I)
  7. #define RREPP(I, A, B) for(int I = (B)-1; I>=A; --I)
  8. #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
  9. #define MP make_pair
  10. #define PB push_back
  11. #define MS0(X) memset((X), 0, sizeof((X)))
  12. #define MS1(X) memset((X), -1, sizeof((X)))
  13. #define LEN(X) strlen(X)
  14. #define F first
  15. #define S second
  16. #define debug(A) REP(i, A.size()) cerr << A[i] << ' '; cerr << '\n'
  17. using namespace std;
  18.  
  19. typedef pair<int, int> ii;
  20. typedef vector<int> vi;
  21. typedef vector<vi> vvi;
  22.  
  23. typedef long long lld;
  24. typedef unsigned long long ulld;
  25. typedef pair<lld, lld> plld;
  26. typedef vector<lld> vlld;
  27. typedef vector<vlld> vvlld;
  28.  
  29. typedef long double ld;
  30. typedef vector<ld> vld;
  31. typedef vector<vld> vvld;
  32.  
  33. const int inf = 987654321;
  34.  
  35. struct Result { int minPsum, maxPsum, maxi; };
  36. Result merge(const Result& a, const Result& b){
  37. 	Result ret;
  38. 	ret.minPsum=min(a.minPsum, b.minPsum);
  39. 	ret.maxPsum=max(a.maxPsum, b.maxPsum);
  40. 	ret.maxi=max( max(a.maxi, b.maxi), b.maxPsum - a.minPsum );
  41. 	return ret;
  42. }
  43. struct snode {
  44.     int i, j; Result res;
  45.     snode *l, *r;
  46.     snode(int i, int j, const vi& arr): i(i), j(j) {
  47.         if (j - i == 1) {
  48.             l = r = NULL;
  49.            	res.maxi = -inf; res.minPsum = res.maxPsum = arr[i];
  50.         } else {
  51.             int k = i + j >> 1;
  52.             l = new snode(i, k, arr);
  53.             r = new snode(k, j, arr);
  54.             res = merge( l->res, r->res );
  55.         }
  56.     }
  57.     ~snode() { delete l, r; }
  58.     Result query(int I, int J) {
  59.         if (I <= i && j <= J) {
  60.             return res;
  61.         } else if (j <= I || J <= i) {
  62.             return {inf, -inf, -inf};
  63.         } else {
  64.             return merge( l->query(I,J), r->query(I,J) );
  65.         }
  66.     }
  67. };
  68.  
  69. struct segment {
  70.     snode *root;
  71.     segment() : root(0) {}
  72.     void init(int n, const vi& arr) {
  73.         if(root) delete root;
  74.         root = new snode(0, n, arr);
  75.     }
  76.     int query(int a, int b, int c, int d) {
  77.     	if(b>c){
  78.     		auto res = root->query(c, b+1);
  79.     		return max( res.maxi,  max(query(a, c, c, d), query(a, b, b, d)) );
  80.     	}else{
  81.     		auto l=root->query(a, b), r=root->query(c+1, d+1);
  82.     		// cout<<r.maxPsum<<"-"<<l.minPsum<<" = ";
  83.     		return r.maxPsum - l.minPsum;
  84.     	}
  85.     }
  86. };
  87. const int MAXN=1e4+10;
  88. int T,N,Q, a,b,c,d; vi arr(MAXN);
  89. int main(){
  90. 	scanf("%d",&T);
  91. 	while(T--){
  92. 		scanf("%d",&N);
  93. 		REP(i, N){ 
  94. 			scanf("%d",&arr[i+1]);
  95. 			arr[i+1]+=arr[i];
  96. 		}
  97. 		segment tree; tree.init(N+1, arr);
  98. 		scanf("%d",&Q);
  99. 		while(Q--){
  100. 			scanf("%d%d%d%d",&a,&b,&c,&d); a--;c--;
  101. 			printf("%d\n", tree.query(a,b,c,d) );
  102. 		}		
  103. 	}
  104.     return 0;
  105. }
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
2
6 3 -2 1 -4 5 2
2
1 1 2 3
1 3 2 5
1 1
1
1 1 1 1
stdout
copy 
2
3
1
https://ideone.com/To5XOG
http://w...content-available-to-author-only...j.com/problems/GSS5/
language:
C++14 (gcc 8.3)
created:
10 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!