Codeforces Round #292 (Div. 2), problem: (E) Drazil and Park

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
#include<cstring>

using namespace std;

typedef pair<int,int> pii;
typedef long long int int64;

struct bst{
    int tree[800000];
    int64 arr[200000];
    int base;
    void init(int n){
        base = (1<<(int)(ceil(log2(n+3)))) - 1;
        for(int lx = 0;lx < n;lx++)
            arr[lx] = 0;
        for(int lx = 0;lx < n;lx++)
            tree[lx + base + 2] = lx;
        for(int lx = base;lx;lx--)
            tree[lx] = tree[lx*2];
        return;
    }
    int rmax(int a, int b){
        return arr[a] > arr[b] ? a:b;
    }
    void set(int p, int64 v){
        arr[p] = v;
        p += base + 2;
        for(p>>=1;p;p>>=1)
            tree[p] = rmax(tree[p*2], tree[p*2 + 1]);
        return;
    }
    int64 get(int p){
        return arr[p];
    }
    int query(int a, int b){
        int ret = a;
        for(a += base+1, b += base+3;a^b^1;a>>=1, b>>=1){
            if(~a&1) ret = rmax(ret, tree[a^1]);
            if(b&1) ret = rmax(ret, tree[b^1]);
        }
        return ret;
    }
    void print(){
        for(int lx = 1;lx <= 2*base + 1;lx++)
            printf("tree %d = %d\n", lx, tree[lx]);
        return;
    }
};

bst mt1, mt2;

int64 d[100000], h[100000];

int main(){
    int n, m; scanf("%d %d", &n, &m);
    for(int lx = 0;lx < n;lx++) scanf("%I64d", d+lx);
    for(int lx = 0;lx < n;lx++) scanf("%I64d", h+lx);
    int64 d_cnt = 0;
    mt1.init(2*n), mt2.init(2*n);
    for(int lx = 0;lx < 2*n;lx++){
        mt1.set(lx, h[lx%n]*2 + d_cnt);
        mt2.set(lx, h[lx%n]*2 - d_cnt);
        //printf("set at %d = %lld, %lld\n", lx, h[lx%n]*2 + d_cnt, h[lx%n]*2 - d_cnt);
        d_cnt += d[lx%n];
    }
    while(m--){
        int a, b; scanf("%d %d", &a, &b);
        a--, b--;
        int na, nb;
        if(a <= b){
            na = b+1, nb = a+n-1;
        }else{
            na = b+1, nb = a-1;
        }
        //printf("q at %d %d\n", na, nb);
        int ida = mt1.query(na, nb); // ida > idb
        int idb = mt2.query(na, nb);
        //printf("first ida = %d, idb = %d\n", ida, idb);
        int64 ans = -1;
        if(ida != idb){
            ans = mt1.get(ida) + mt2.get(idb);
            //printf("ida = %d, idb = %d\n", ida, idb);
        }else{
            int tmp = ida;
            if(idb+1 <= nb){
                ida = mt1.query(idb+1, nb);
                ans = mt1.get(ida) + mt2.get(idb);
                //printf("ida = %d, idb = %d\n", ida, idb);
            }
            ida = tmp;
            if(ida-1 >= na){
                idb = mt2.query(na, ida-1);
                ans = max(ans, mt1.get(ida) + mt2.get(idb));
                //printf("ida = %d, idb = %d\n", ida, idb);
            }
        }
        printf("%I64d\n",ans); 
    }
    return 0;
}