fork download
copy 
  1. #include <cstdio>
  2. #define ls(root) root << 1
  3. #define rs(root) root << 1 | 1
  4. #define max(__a, __b) [&](int _a, int _b) {return _a > _b ? _a : _b;} ((__a), (__b))
  5.  
  6. const int MAXN = 5e4 + 10;
  7.  
  8. struct NODE {
  9.   int sum;
  10.   int maxsub;
  11.   int prefix;
  12.   int suffix;
  13. } node[MAXN << 2];
  14.  
  15. int n, m;
  16. int a[MAXN];
  17.  
  18. void PushUp(int root) {
  19.   node[root].sum = node[ls(root)].sum + node[rs(root)].sum;
  20.   node[root].prefix = max(node[ls(root)].prefix, node[ls(root)].sum + node[rs(root)].prefix);
  21.   node[root].suffix = max(node[rs(root)].suffix, node[rs(root)].sum + node[ls(root)].suffix);
  22.   node[root].maxsub = max(max(node[ls(root)].maxsub, node[rs(root)].maxsub), node[ls(root)].suffix + node[rs(root)].prefix);
  23. }
  24.  
  25. void Build(int root, int lt, int rt) {
  26.   if (lt == rt) {
  27.     node[root].sum = a[lt];
  28.     node[root].maxsub = a[lt];
  29.     node[root].prefix = a[lt];
  30.     node[root].suffix = a[lt];
  31.     return ;
  32.   }
  33.   int mid = lt + ((rt - lt) >> 1);
  34.   Build(ls(root), lt, mid);
  35.   Build(rs(root), mid + 1, rt);
  36.   PushUp(root);
  37. }
  38.  
  39. NODE Query(int root, int lt, int rt, int lq, int rq) {
  40.   if (lt == lq && rt == rq) {
  41.     return node[root];
  42.   }
  43.   int mid = lt + ((rt - lt) >> 1);
  44.   if (rq <= mid) {
  45.     return Query(ls(root), lt, mid, lq, rq);
  46.   } else if (lq > mid) {
  47.     return Query(rs(root), mid + 1, rt, lq, rq);
  48.   } else {
  49.     NODE ans, ln = Query(ls(root), lt, mid, lq, mid), rn = Query(rs(root), mid + 1, rt, mid + 1, rq);
  50.     ans.sum = ln.sum + rn.sum;
  51.     ans.prefix = max(ln.prefix, ln.sum + rn.prefix);
  52.     ans.suffix = max(rn.suffix, ln.suffix + rn.sum);
  53.     ans.maxsub = max(max(ln.maxsub, rn.maxsub), ln.suffix + rn.suffix);
  54.     return ans;
  55.   }
  56. }
  57.  
  58. int main() {
  59.   scanf("%d", &n);
  60.   for (int i = 1; i <= n; ++i) {
  61.     scanf("%d", &a[i]);
  62.   }
  63.   Build(1, 1, n);
  64.   scanf("%d", &m);
  65.   while (m--) {
  66.     int l, r;
  67.     scanf("%d %d", &l, &r);
  68.     printf("%d\n", Query(1, 1, n, l ,r).maxsub);
  69.   }
  70.   return 0;
  71. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/pAk50T
problem GSS1, based on SPOJ submission 34656425 (CPP14), 2025-05-29 14:40:21
language:
C++14 (gcc 8.3)
created:
18 days 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!