fork(1) download
copy 
  1. //tonynater - SPOJ 2013
  2.  
  3. #include <algorithm>
  4. #include <bitset>
  5. #include <cassert>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <fstream>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <list>
  12. #include <map>
  13. #include <queue>
  14. #include <set>
  15. #include <sstream>
  16. #include <stack>
  17. #include <string>
  18. #include <vector>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <string.h>
  22.  
  23. using namespace std;
  24.  
  25. #define sz(x) ((int) x.size())
  26.  
  27. typedef long double ld;
  28. typedef long long ll;
  29. typedef pair<int, int> pii;
  30.  
  31. const double pi = 3.141592653589793;
  32. const double tau = 6.283185307179586;
  33. const double epsilon = 1e-6;
  34.  
  35. const int MAX_N = 50100;
  36. const int MIN_VALUE = -(1<<30);
  37.  
  38. int N, M;
  39.  
  40. int A[MAX_N];
  41.  
  42. struct segment
  43. {
  44.     int tMax;
  45.     int lMax;
  46.     int rMax;
  47.     int sum;
  48.  
  49.     segment()
  50.     {
  51.         tMax = lMax = rMax = sum = 0;
  52.     }
  53.  
  54.     segment(int t, int l, int r, int s)
  55.     {
  56.         tMax = t;
  57.         lMax = l;
  58.         rMax = r;
  59.         sum = s;
  60.     }
  61. };
  62.  
  63. segment tree[MAX_N*3];
  64.  
  65. segment merge(segment s1, segment s2) //s1 left of s2
  66. {
  67.     int tMax = max(s1.rMax+s2.lMax, max(s1.tMax, s2.tMax));
  68.     int lMax = max(s1.sum + s2.lMax, s1.lMax);
  69.     int rMax = max(s2.sum + s1.rMax, s2.rMax);
  70.     int sum = s1.sum + s2.sum;
  71.  
  72.     return segment(tMax, lMax, rMax, sum);
  73. }
  74.  
  75. void build(int n, int b, int e)
  76. {
  77.     if(b == e) tree[n] = segment(A[b], A[b], A[b], A[b]);
  78.     else
  79.     {
  80.         build(2*n, b, (b+e)/2);
  81.         build(2*n+1, (b+e)/2+1, e);
  82.  
  83.         tree[n] = merge(tree[2*n], tree[2*n+1]);
  84.     }
  85. }
  86.  
  87. segment query(int n, int b, int e, int x, int y)
  88. {
  89.     if(b > e || b > y || e < x) return segment(MIN_VALUE, MIN_VALUE, MIN_VALUE, MIN_VALUE);
  90.     else if(x <= b && e <= y) return tree[n];
  91.     else return merge(query(2*n, b, (b+e)/2, x, y), query(2*n+1, (b+e)/2+1, e, x, y));
  92. }
  93.  
  94. int main (int argc, const char * argv[])
  95. {
  96.     ios_base::sync_with_stdio(0);
  97.     cin.tie(NULL);
  98.  
  99.     cin >> N;
  100.  
  101.     for(int i = 0; i < N; i++)
  102.         cin >> A[i];
  103.  
  104.     build(1, 0, N-1);
  105.  
  106.     cin >> M;
  107.  
  108.     for(int i = 0; i < M; i++)
  109.     {
  110.         int x, y;
  111.         cin >> x >> y;
  112.         --x; --y;
  113.  
  114.         cout << query(1, 0, N-1, x, y).tMax << '\n';
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
Runtime error #stdin #stdout 0s 13640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vcCrHZ
language:
C++ (gcc 8.3)
created:
11 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!