Submission #440222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440222	2021-07-01T19:09:34 Z	izhang05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	394 ms	200080 KB

apple

#include <bits/stdc++.h>

using namespace std;

//#define DEBUG
void setIO(const string &name) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.exceptions(istream::failbit);
#ifdef LOCAL
    freopen((name + ".in").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
    freopen((name + ".out").c_str(), "w", stderr);
#endif
}
struct node {
    int sum, lazy, lx{}, rx{}, lc, rc;
    node() : sum(0), lazy(0), lc(-1), rc(-1) {}
};

struct segtree {
    int size = 1, cnt = 1;
    vector<node> t;

    void init(int n) {
        while (size < n) {
            size *= 2;
        }
        t.resize(64 * size);
    }

    void create(int x) {
        int m = (t[x].lx + t[x].rx) / 2;
        if (t[x].lc == -1) {
            t[x].lc = cnt++;
            t[t[x].lc].lx = t[x].lx;
            t[t[x].lc].rx = m;
        }
        if (t[x].rc == -1) {
            t[x].rc = cnt++;
            t[t[x].rc].lx = m;
            t[t[x].rc].rx = t[x].rx;
        }
    }

    void propagate(int x) {
        if (t[x].rx - t[x].lx == 1) {
            return;
        }
        if (t[x].lazy) {
            int m = (t[x].lx + t[x].rx) / 2;
            create(x);
            t[t[x].lc].sum = m - t[x].lx;
            t[t[x].rc].sum = t[x].rx - m;
            t[t[x].lc].lazy = t[t[x].rc].lazy = 1;
            t[x].lazy = 0;
        }
    }

    void upd(int x, int l, int r) {
        if (t[x].lx >= r || t[x].rx <= l) {
            return;
        }
        if (t[x].lx >= l && t[x].rx <= r) {
            t[x].lazy = 1;
            t[x].sum = t[x].rx - t[x].lx;
            return;
        }
        propagate(x);
        create(x);
        upd(t[x].lc, l, r), upd(t[x].rc, l, r);
        t[x].sum = t[t[x].lc].sum + t[t[x].rc].sum;
    }

    int query(int x, int l, int r) {
        if (t[x].lx >= r || t[x].rx <= l) {
            return 0;
        }
        if (t[x].lx >= l && t[x].rx <= r) {
            return t[x].sum;
        }
        propagate(x);
        create(x);
        return query(t[x].lc, l, r) + query(t[x].rc, l, r);
    }
};

const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

int main() {
    setIO("1");

    int m;
    cin >> m;
    segtree seg;
    seg.init(m);
    seg.t[0].lx = 0, seg.t[0].rx = 1e9;
    int c = 0;
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        --x, --y;
        if (t == 1) {
            c = seg.query(0, x + c, y + c + 1);
            cout << c << "\n";
        } else {
            seg.upd(0, x + c, y + c + 1);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	460 KB	Output is correct
4	Correct	18 ms	12776 KB	Output is correct
5	Correct	29 ms	25040 KB	Output is correct
6	Correct	29 ms	25128 KB	Output is correct
7	Correct	27 ms	25084 KB	Output is correct
8	Correct	149 ms	99832 KB	Output is correct
9	Correct	315 ms	199400 KB	Output is correct
10	Correct	377 ms	199332 KB	Output is correct
11	Correct	327 ms	199432 KB	Output is correct
12	Correct	348 ms	199468 KB	Output is correct
13	Correct	303 ms	199864 KB	Output is correct
14	Correct	300 ms	199776 KB	Output is correct
15	Correct	386 ms	199900 KB	Output is correct
16	Correct	390 ms	200028 KB	Output is correct
17	Correct	330 ms	199796 KB	Output is correct
18	Correct	314 ms	199880 KB	Output is correct
19	Correct	380 ms	199924 KB	Output is correct
20	Correct	394 ms	200080 KB	Output is correct