Submission #526249

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526249	2022-02-14T04:10:48 Z	BackNoob	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	294 ms	153664 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	150860 KB	Output is correct
2	Correct	74 ms	150852 KB	Output is correct
3	Correct	65 ms	150932 KB	Output is correct
4	Correct	72 ms	151016 KB	Output is correct
5	Correct	74 ms	151108 KB	Output is correct
6	Correct	82 ms	151204 KB	Output is correct
7	Correct	72 ms	151076 KB	Output is correct
8	Correct	160 ms	151960 KB	Output is correct
9	Correct	237 ms	153020 KB	Output is correct
10	Correct	244 ms	153032 KB	Output is correct
11	Correct	242 ms	153060 KB	Output is correct
12	Correct	255 ms	153076 KB	Output is correct
13	Correct	217 ms	153384 KB	Output is correct
14	Correct	223 ms	153412 KB	Output is correct
15	Correct	290 ms	153560 KB	Output is correct
16	Correct	279 ms	153536 KB	Output is correct
17	Correct	242 ms	153468 KB	Output is correct
18	Correct	232 ms	153440 KB	Output is correct
19	Correct	294 ms	153596 KB	Output is correct
20	Correct	289 ms	153664 KB	Output is correct