Submission #440238

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440238	2021-07-01T19:29:34 Z	izhang05	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	400 ms	197828 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	23 ms	12644 KB	Output is correct
5	Correct	28 ms	24964 KB	Output is correct
6	Correct	31 ms	24916 KB	Output is correct
7	Correct	27 ms	24964 KB	Output is correct
8	Correct	145 ms	98884 KB	Output is correct
9	Correct	324 ms	197612 KB	Output is correct
10	Correct	352 ms	197680 KB	Output is correct
11	Correct	354 ms	197692 KB	Output is correct
12	Correct	334 ms	197656 KB	Output is correct
13	Correct	306 ms	197828 KB	Output is correct
14	Correct	292 ms	197792 KB	Output is correct
15	Correct	370 ms	197752 KB	Output is correct
16	Correct	347 ms	197728 KB	Output is correct
17	Correct	324 ms	197828 KB	Output is correct
18	Correct	305 ms	197684 KB	Output is correct
19	Correct	400 ms	197784 KB	Output is correct
20	Correct	369 ms	197748 KB	Output is correct