Submission #874367

#	Time	Username	Problem	Language	Result	Execution time	Memory
874367		andrei_marciuc	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	314 ms	123184 KiB

apple

#include <iostream>
 
using namespace std;
 
const int NMAX = 1e9;
 
struct node {
    node *lft, *rgt;
    bool lazy;
    bool todost;
    bool tododr;
    int ans;
 
    node() {
        lft = rgt = NULL;
        lazy = 0;
        ans = 0;
        todost = 0;
        tododr = 0;
    }
};
 
void create(node *nod, bool ok) {
    if(ok == 0) {
        if(nod->lft == NULL)
            nod->lft = new node();
        if(nod->todost)
            nod->lft->lazy = true;
        nod->todost = 0;
    } else {
        if(nod->rgt == NULL)
            nod->rgt = new node();
        if(nod->tododr)
            nod->rgt->lazy = true;
        nod->tododr = 0;
    }
}
 
void propag(node *nod, int st, int dr ){
    if(nod->lazy == true) {
        nod->ans = dr - st + 1;
        nod->todost = 1;
        nod->tododr = 1;
    }
    nod->lazy = 0;
}
 
void update(node *nod, int st, int dr, int a, int b) {
    propag(nod, st, dr);
    if(a <= st and dr <= b) {
        nod->lazy = 1;
        propag(nod, st, dr);
        return ;
    }

    int med = ((st + dr) >> 1);
    if(a <= med) {
        create(nod, 0);
        update(nod->lft, st, med, a, b);
    }

    if(b > med) {
        create(nod, 1);
        update(nod->rgt, med + 1, dr, a, b);
    }

    nod->ans = 0;
    if(nod->todost) {
        create(nod, 0);
        propag(nod->lft, st, med);
    }

    if(nod->lft != NULL)
        nod->ans += nod->lft->ans;
    if(nod->tododr) {
        create(nod, 1);
        propag(nod->rgt, med + 1, dr);
    }

    if(nod->rgt != NULL)
        nod->ans += nod->rgt->ans;
}
 
int query(node *nod, int st, int dr, int a, int b) {
    propag(nod, st, dr);
    if(a <= st and dr <= b) {
        return nod->ans;
    }

    int med = ((st + dr) >> 1);
    int ans = 0;

    if(a <= med) {
        create(nod, 0);
        if(nod->lft != NULL) {
            ans += query(nod->lft, st, med, a, b);
        }
    }

    if(b > med) {
        create(nod, 1);
        if(nod->rgt != NULL) {
            ans += query(nod->rgt, med + 1, dr, a, b);
        }
    }
    return ans;
}
 
 
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    node *nod = new node();
    
    while(n--) {
        int op, a, b;
        cin >> op >> a >> b;
        a += ans;
        b += ans;
        if(op == 1) {
            int val = query(nod, 1, NMAX, a, b);
            cout << val << "\n";
            ans = val;
        } else update(nod, 1, NMAX, a, b);
    }
    return 0;
}

• Subtask 1: 100 / 100