Submission #531303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531303	2022-02-28T11:21:12 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	433 ms	262148 KB

apple

#include <bits/stdc++.h>
using namespace std;

class DynamicSegTree
{
    struct DSegTreeItem
    {
        int val;
        bool lazy;
        DSegTreeItem *l, *r;
    };

  public:
    DynamicSegTree(int n)
    {
        this->nodes.reserve(32 * 1e5);
        this->make_new();
        this->size = n;
    }
    void rangeUpdate(int x, int y, int v, DSegTreeItem *cur, int l, int r)
    {
        if (cur->lazy)
            propagateLazy(cur, l, r);

        if (y <= l || x >= r)
            return;
        if (l >= x && r <= y)
        {
            cur->lazy = v;
            propagateLazy(cur, l, r);
            return;
        }

        dynamics(cur);
        rangeUpdate(x, y, v, cur->l, l, (r + l) / 2);
        rangeUpdate(x, y, v, cur->r, (r + l) / 2, r);

        cur->val = cur->l->val + cur->r->val;
    }
    int query(int x, int y, DSegTreeItem *cur, int l, int r)
    {
        if (cur->lazy)
            propagateLazy(cur, l, r);

        if (y <= l || x >= r)
            return 0;
        if (l >= x && r <= y)
            return cur->val;

        dynamics(cur);
        return query(x, y, cur->l, l, (r + l) / 2) + query(x, y, cur->r, (r + l) / 2, r);
    }
    void rangeUpdate(int x, int y, int v)
    {
        rangeUpdate(x, y, v, nodes[0], 0, size);
    }
    int query(int x, int y)
    {
        return query(x, y, nodes[0], 0, size);
    }

  private:
    int size;
    vector<DSegTreeItem *> nodes;
    DSegTreeItem *make_new()
    {
        DSegTreeItem *nw = new DSegTreeItem({0, 0, nullptr, nullptr});
        nodes.push_back(nw);
        return nw;
    }
    void dynamics(DSegTreeItem *cur)
    {
        if (cur->l == nullptr)
            cur->l = make_new();

        if (cur->r == nullptr)
            cur->r = make_new();
    }
    void propagateLazy(DSegTreeItem *cur, int l, int r)
    {
        if (l != r - 1)
        {
            dynamics(cur);
            cur->l->lazy = cur->lazy;
            cur->r->lazy = cur->lazy;
        }
        cur->val = (r - l) * cur->lazy, cur->lazy = 0;
    }
};

void solveCase()
{
    int m = 0;
    cin >> m;

    DynamicSegTree dst(1e9 + 1);

    int c = 0;
    while (m--)
    {
        int d = 0, x = 0, y = 0;
        cin >> d >> x >> y;
        if (d == 1)
            c = dst.query(x + c, y + c + 1), cout << c << '\n';
        else
            dst.rangeUpdate(x + c, y + c + 1, 1);
    }
}

int32_t main()
{
    mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());
    if (rng() % 100000 == 0)
        assert(false);

    ios::sync_with_stdio(false), cin.tie(NULL);
    solveCase();
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	328 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	17 ms	7176 KB	Output is correct
5	Correct	22 ms	8656 KB	Output is correct
6	Correct	21 ms	8324 KB	Output is correct
7	Correct	18 ms	8652 KB	Output is correct
8	Correct	145 ms	64196 KB	Output is correct
9	Correct	295 ms	109040 KB	Output is correct
10	Correct	356 ms	122536 KB	Output is correct
11	Correct	328 ms	150888 KB	Output is correct
12	Correct	342 ms	150956 KB	Output is correct
13	Correct	323 ms	170952 KB	Output is correct
14	Correct	330 ms	172924 KB	Output is correct
15	Runtime error	433 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-