Advertisement
YEZAELP

o60_oct_c1_house

Dec 27th, 2021
1,014
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 2e5 + 10;
  5. int ar[N];
  6.  
  7. typedef struct Node{
  8.     int frnt, bck, total, mx;
  9. };
  10.  
  11. Node tree[524288];
  12.  
  13. Node Cal(Node L, Node R){
  14.     Node cur;
  15.     cur.frnt = max(L.frnt, L.total + R.frnt);
  16.     cur.bck = max(R.bck, R.total + L.bck);
  17.     cur.total = L.total + R.total;
  18.     cur.mx = max({L.mx, R.mx, L.bck + R.frnt});
  19.     return cur;
  20. }
  21.  
  22. void Build(int idx, int l, int r){
  23.     if(l == r){
  24.         tree[idx].bck = tree[idx].frnt = tree[idx].total = tree[idx].mx = ar[l];
  25.         return;
  26.     }
  27.     int mid = (l + r) / 2;
  28.     Build(2 * idx, l, mid);
  29.     Build(2 * idx + 1, mid + 1, r);
  30.     tree[idx] = Cal(tree[2 * idx], tree[2 * idx + 1]);
  31. }
  32.  
  33. Node Query(int idx, int l, int r, int s, int e){
  34.     if(l > e or r < s) return {0, 0, 0, 0};
  35.     if(s <= l and r <= e) return tree[idx];
  36.     int mid = (l + r) / 2;
  37.     return Cal( Query(2 * idx, l, mid, s, e) , Query(2 * idx + 1, mid + 1, r, s, e) );
  38. }
  39.  
  40. int main(){
  41.  
  42.     int n, Q;
  43.     scanf("%d %d", &n, &Q);
  44.  
  45.     for(int i=1;i<=n;i++){
  46.         scanf("%d", &ar[i]);
  47.     }
  48.  
  49.     Build(1, 1, n);
  50.  
  51.     for(int q=1;q<=Q;q++){
  52.         int a, b;
  53.         scanf("%d %d", &a, &b);
  54.         a ++, b ++;
  55.  
  56.         Node query = Query(1, 1, n, a, b);
  57.         printf("%d\n", query.mx);
  58.  
  59.         /*int ans = 0;
  60.         int dpp = 0;
  61.         for(int i=a;i<=b;i++){
  62.             int dpc = max(dpp + ar[i], ar[i]);
  63.             dpp = dpc;
  64.             ans = max(ans, dpc);
  65.         }
  66.         printf("%d\n", ans);*/
  67.     }
  68.  
  69.     return 0;
  70. }
Advertisement
RAW Paste Data Copied
Advertisement