Submission #531307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531307	2022-02-28T11:28:18 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	414 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(64 * 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	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	15 ms	7212 KB	Output is correct
5	Correct	22 ms	8652 KB	Output is correct
6	Correct	18 ms	8400 KB	Output is correct
7	Correct	20 ms	8652 KB	Output is correct
8	Correct	157 ms	64256 KB	Output is correct
9	Correct	289 ms	109124 KB	Output is correct
10	Correct	320 ms	122448 KB	Output is correct
11	Correct	314 ms	132932 KB	Output is correct
12	Correct	319 ms	137360 KB	Output is correct
13	Correct	324 ms	170944 KB	Output is correct
14	Correct	309 ms	172832 KB	Output is correct
15	Runtime error	414 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-