Submission #526249

#	Time	Username	Problem	Language	Result	Execution time	Memory
526249		BackNoob	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	294 ms	153664 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 1e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct Node{
    int sum , lz , tl , tr , l , r;
    Node() : sum(0) , lz(0) , l(-1) , r(-1) {}
} t[mxN * 64];

int cnt = 1;

void modify(int v , int tl , int tr)
{
    int tm = (tl + tr) / 2;
    if(t[v].lz == 1) {
        if(t[v].l == -1) {
            t[v].l = ++cnt;
            t[cnt].tl = tl;
            t[cnt].tr = tm;
        }
        if(t[v].r == -1) {
            t[v].r = ++cnt;
            t[cnt].tl = tm + 1;
            t[cnt].tr = tr;
        }

        int lef = t[v].l;
        int rig = t[v].r;
        t[lef].sum = tm - tl + 1;
        t[rig].sum = tr - tm;
        t[lef].lz = t[rig].lz = true;
    }
    t[v].lz = 0;
}

void update(int v , int l , int r)
{
    //cerr << v << ' ' << l << ' ' << r << endl;
    if(l > r) return;
    int tl = t[v].tl;
    int tr = t[v].tr;
    //cerr << v << ' ' << tl << ' ' << tr << ' ' << l << ' ' << r << endl;
    if(tl == l && tr == r) {
        t[v].sum = (tr - tl + 1);
        t[v].lz = true;
    }
    else {
        modify(v , tl , tr);
        int tm = (tl + tr) / 2;
        if(t[v].l == -1) {
            t[v].l = ++cnt;
            t[cnt].tl = tl;
            t[cnt].tr = tm;
        }
        if(t[v].r == -1) {
            t[v].r = ++cnt;
            t[cnt].tl = tm + 1;
            t[cnt].tr = tr;
        }
        update(t[v].l , l , min(tm , r));
        update(t[v].r , max(l , tm + 1) , r);
        t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    }
}

int getsum(int v , int l , int r)
{
    if(l > r) return 0;
    int tl = t[v].tl;
    int tr = t[v].tr;
    //cerr << tl << ' ' << tr << ' ' << l << ' ' << r << endl;
    if(tl == l && tr == r) return t[v].sum;
    modify(v , tl , tr);
    int tm = (tl + tr) / 2;
    if(t[v].l == -1) {
        t[v].l = ++cnt;
        t[cnt].tl = tl;
        t[cnt].tr = tm;
    }
    if(t[v].r == -1) {
        t[v].r = ++cnt;
        t[cnt].tl = tm + 1;
        t[cnt].tr = tr;
    }
    int m1 = getsum(t[v].l , l , min(r , tm));
    int m2 = getsum(t[v].r , max(l , tm + 1) , r);
    return m1 + m2;
}

int q;

void solve()
{
    int c = 0;
    t[1].tl = 1;
    t[1].tr = 1e9;
    cin >> q;
    while(q--) {
        int cmd , x , y;
        cin >> cmd >> x >> y;
        x += c;
        y += c;
        if(cmd == 2) {
            update(1 , x , y);
        }
        else {
            c = getsum(1 , x , y);
            cout << c << endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

• Subtask 1: 100 / 100