Submission #795940

#	Time	Username	Problem	Language	Result	Execution time	Memory
795940		idiotcomputer	Monkey and Apple-trees (IZhO12_apple)	C++11	0 / 100	97 ms	235104 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct node {
    int sum = 0;
    int l = -1;
    int r = -1;
    int tl,tr;
    bool has = false;
};

const int MAX_N = 2500000;
const int MAX_V = 1e9;

int cnt = 0;
node segt[4*MAX_N+1];

void timeout(){
    if (cnt >= 4*MAX_N+1){
        while (true){
            cnt += 1;
        }
    }    
}

void push(int idx){
    if (segt[idx].has){
        segt[idx].sum = segt[idx].tr - segt[idx].tl + 1;
        int mid = (segt[idx].tl + segt[idx].tr)/2;
        if (segt[idx].l == -1){
            segt[idx].l = cnt;
            cnt ++;
            timeout();
            segt[segt[idx].l].tl = segt[idx].tl;
            segt[segt[idx].l].tr = mid;
        }
        if (segt[idx].r == -1){
            segt[idx].r = cnt;
            cnt ++;
            timeout();
            segt[segt[idx].r].tl = mid+1;
            segt[segt[idx].r].tr = segt[idx].tr;
        }
        segt[idx].has = 0;
        segt[segt[idx].r].has = 1;
        segt[segt[idx].l].has = 1;
    }    
}

void upd(int idx, int tl, int tr){
    push(idx);
    if (segt[idx].tl > tr || segt[idx].tr < tl){
        return;
    }
    if (segt[idx].tl >= tl && segt[idx].tr <= tr){
        segt[idx].has = true;
        push(idx);
        return;
    }
    int mid = (segt[idx].tl + segt[idx].tr)/2;
    if (segt[idx].l == -1){
        segt[idx].l = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].l].tl = segt[idx].tl;
        segt[segt[idx].l].tr = mid;
    }
    if (segt[idx].r == -1){
        segt[idx].r = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].r].tl = mid+1;
        segt[segt[idx].r].tr = segt[idx].tr;
    }
    upd(segt[idx].l,tl,tr);
    upd(segt[idx].r,tl,tr);

    //setting sum
    int cl = segt[idx].l;
    int cr = segt[idx].r;
    segt[idx].sum = segt[cl].sum + segt[cr].sum;
    return;
}

int query(int idx, int tl, int tr){
    push(idx);
    if (segt[idx].tl > tr || segt[idx].tr < tl){
        return 0;
    }
    if (segt[idx].tl >= tl && segt[idx].tr <= tr){
        return segt[idx].sum;
    }
    int mid = (segt[idx].tr + segt[idx].tl)/2;
    if (segt[idx].l == -1){
        segt[idx].l = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].l].tl = segt[idx].tl;
        segt[segt[idx].l].tr = mid;
    }
    if (segt[idx].r == -1){
        segt[idx].r = cnt;
        cnt ++;
        timeout();
        segt[segt[idx].r].tl = mid+1;
        segt[segt[idx].r].tr = segt[idx].tr;
    }
        
    return query(segt[idx].l,tl,tr)+query(segt[idx].r,tl,tr);
    
}

int main()
{
    int m;
    cin >> m;
    
    int d,x,y;
    segt[0].tl = 1;
    segt[0].tr = MAX_V;
    cnt ++;
    int c = 0;
    int res;
    
    for (int i =0; i < m; i++){
        cin >> d >> x >> y;
        if (d == 1){
      //      cout << c << ": ";
            res = query(0,x+c,y+c);
            c += res;
            cout << res << '\n';
        } else {
            upd(0,x+c,y+c);
        }
    }
    
    //cout << MAX_V << " " << MAX_N << '\n';
    return 0;
}

• Subtask 1: 0 / 100