Submission #667255

#	Time	Username	Problem	Language	Result	Execution time	Memory
667255		divad	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	541 ms	207708 KiB

apple

/// aint dinamic / implicit
#include <iostream>
//#define int long long
#define MAX 1000000000
using namespace std;
int m,t,x,y,sol,c;

struct nod{
    int st, dr;
    int sum;
    bool lazy;
    nod *fiu_st, *fiu_dr;

    nod(int x, int y){
        st = x;
        dr = y;
        sum = 0;
        lazy = false;
        fiu_st = fiu_dr = NULL;
    }
};

void propag(nod *&tata, nod *&fiu_st, nod *&fiu_dr, int st, int dr){
    if(st == dr){
        return ;
    }
    if(tata->lazy == false){
        /// nu e nevoie
        return ;
    }
    int mid = (st+dr)/2;
    if(fiu_st == NULL){
        fiu_st = new nod(st, mid);
    }
    if(fiu_dr == NULL){
        fiu_dr = new nod(mid+1, dr);
    }
    fiu_st->lazy = fiu_dr->lazy = true;
    tata->lazy = false;
    fiu_st->sum = (fiu_st->dr - fiu_st->st + 1);
    fiu_dr->sum = (fiu_dr->dr - fiu_dr->st + 1);
}

void query(nod *&tata, int st, int dr, int a, int b){
    if(tata == NULL){
        return ;
    }
    if(a <= st && dr <= b){
        sol += tata->sum;
    }else{
        int mid = (st+dr)/2;
        propag(tata, tata->fiu_st, tata->fiu_dr, st, dr);
        if(a <= mid){
            query(tata->fiu_st, st, mid, a, b);
        }
        if(b >= mid+1){
            query(tata->fiu_dr, mid+1, dr, a, b);
        }
    }
}
nod *aint;

void update(nod *&tata, int st, int dr, int a, int b){
    if(tata == NULL){
        tata = new nod(st, dr);
    }
    if(a <= st && dr <= b){
        tata->sum = dr-st+1;
        tata->lazy = true;
    }else{
        propag(tata, tata->fiu_st, tata->fiu_dr, st, dr);
        int mid = (st+dr)/2;
        if(a <= mid){
            update(tata->fiu_st, st, mid, a, b);
        }
        if(b >= mid+1){
            update(tata->fiu_dr, mid+1, dr, a, b);
        }
        int sum_st = 0, sum_dr = 0;
        if(tata->fiu_st != NULL){
            sum_st = tata->fiu_st->sum;
        }
        if(tata->fiu_dr != NULL){
            sum_dr = tata->fiu_dr->sum;
        }
        tata->sum = sum_st+sum_dr;
    }
}

signed main()
{
    aint = new nod(1, MAX);
    cin >> m;
    while(m--){
        cin >> t >> x >> y;
        x += c; y += c;
        if(t == 1){
            sol = 0;
            query(aint, 1, MAX, x, y);
            cout << sol << "\n";
            c = sol;
        }else{
            update(aint, 1, MAX, x, y);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100