fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstring>
  5. #include <complex>
  6. #include <cassert>
  7. #include <cstdlib>
  8. #include <cstdio>
  9. #include <bitset>
  10. #include <vector>
  11. #include <string>
  12. #include <cmath>
  13. #include <ctime>
  14. #include <stack>
  15. #include <queue>
  16. #include <list>
  17. #include <map>
  18. #include <set>
  19.  
  20. #define all(x) (x).begin(), (x).end()
  21. #define type(x) __typeof((x).begin())
  22. #define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
  23.  
  24. #ifdef KAZAR
  25.     #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  26. #else
  27.     #define eprintf(...) 0
  28. #endif
  29.  
  30. using namespace std;
  31.  
  32. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  33. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  34. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  35. template<class T> inline T gcd(T a,T b){return __gcd(a, b);}
  36. template<class T> inline T lcm(T a,T b){return a/gcd(a,b)*b;}
  37.  
  38. typedef long long ll;
  39. typedef pair<int, int> ii;
  40.  
  41. const int inf = 1e9 + 143;
  42. const ll longinf = 1e18 + 143;
  43.  
  44. inline int read(){int x;scanf(" %d",&x);return x;}
  45.  
  46. const int N = 50500;
  47. const int M = 1e6 + 100;
  48. const int BLOCK = 400;
  49.  
  50. int a[N];
  51. int ps[N];
  52.  
  53. int l[M], r[M];
  54. int ans[M];
  55.  
  56. vector<int> q[N / BLOCK + 5];
  57.  
  58. bool byr(const int &a,const int &b){
  59.     return r[a] < r[b];
  60. }
  61.  
  62. int main(){
  63.  
  64. #ifdef KAZAR
  65.     freopen("f.input","r",stdin);
  66.     freopen("f.output","w",stdout);
  67.     freopen("error","w",stderr);
  68. #endif
  69.  
  70.     int n = read();
  71.  
  72.     for(int i = 0; i < n; i++){
  73.         a[i] = read();
  74.         ps[i] = ps[i - 1] + a[i];
  75.     }
  76.  
  77.     int m = read();
  78.  
  79.     for(int i = 0; i < m; i++){
  80.         l[i] = read() - 1;
  81.         r[i] = read() - 1;
  82.         ans[i] = -inf;
  83.         q[l[i] / BLOCK].push_back(i);
  84.     }
  85.  
  86.     for(int it = 0; it * BLOCK < n; it++){
  87.         int from = it * BLOCK;
  88.         int to = from + BLOCK - 1;
  89.         sort(all(q[it]), byr);
  90.         int ptr = to + 1, max_ps = -inf, min_ps = ps[to], max_sum = -inf;
  91.         foreach(qit, q[it]){
  92.             int id = *qit;
  93.             int r = ::r[id];
  94.             int l = ::l[id];
  95.             if(r <= to){
  96.                 int lval = ps[l - 1];
  97.                 for(int j = l; j <= r; j++){
  98.                     umax(ans[id], ps[j] - lval);
  99.                     umin(lval, ps[j]);
  100.                 }
  101.             }else{
  102.                 while(ptr <= r){
  103.                     umax(max_sum, ps[ptr] - min_ps);
  104.                     umax(max_ps, ps[ptr]);
  105.                     umin(min_ps, ps[ptr]);
  106.                     ptr++;
  107.                 }
  108.                 int lval = ps[l - 1];
  109.                 for(int i = l; i <= to; i++){
  110.                     umax(ans[id], ps[i] - lval);
  111.                     umin(lval, ps[i]);
  112.                 }
  113.                 umax(ans[id], max_ps - lval);
  114.                 umax(ans[id], max_sum);
  115.             }
  116.         }
  117.     }
  118.  
  119.     for(int i = 0; i < m; i++){
  120.         printf("%d\n", ans[i]);
  121.     }
  122.  
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0s 15464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4ebaBF
language:
C++ (gcc 8.3)
created:
10 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!