Submission #440236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440236	2021-07-01T19:29:07 Z	izhang05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	489 ms	262148 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(32 * 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

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	332 KB	Output is correct
4	Correct	15 ms	6508 KB	Output is correct
5	Correct	26 ms	12560 KB	Output is correct
6	Correct	25 ms	12652 KB	Output is correct
7	Correct	23 ms	12668 KB	Output is correct
8	Correct	135 ms	49688 KB	Output is correct
9	Correct	266 ms	99308 KB	Output is correct
10	Correct	264 ms	99172 KB	Output is correct
11	Correct	262 ms	99184 KB	Output is correct
12	Correct	283 ms	99160 KB	Output is correct
13	Correct	243 ms	99268 KB	Output is correct
14	Correct	244 ms	99184 KB	Output is correct
15	Runtime error	489 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-