Submission #531289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531289	2022-02-28T10:58:24 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	428 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(1e6);
        this->make_new();
        this->size = n;
    }
    void rangeUpdate(int x, int y, DSegTreeItem *cur, int l, int r)
    {
        dynamics(cur);
        if (cur->lazy)
            propagateLazy(cur, l, r);
        if (y <= l || x >= r)
            return;
        if (l >= x && r <= y)
        {
            cur->lazy = 1;
            propagateLazy(cur, l, r);
            return;
        }
        rangeUpdate(x, y, cur->l, l, (r + l) / 2);
        rangeUpdate(x, y, 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)
    {
        dynamics(cur);
        if (cur->lazy)
            propagateLazy(cur, l, r);
        if (y <= l || x >= r)
            return 0;
        if (l >= x && r <= y)
            return cur->val;
        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)
    {
        rangeUpdate(x, y, 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 *nx = new DSegTreeItem({0, 0, nullptr, nullptr});
        nodes.push_back(nx);
        return nodes.back();
    }
    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)
        {
            cur->l->lazy = 1;
            cur->r->lazy = 1;
        }
        cur->val = r - l;
        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);
    }
}

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	328 KB	Output is correct
4	Correct	16 ms	7868 KB	Output is correct
5	Correct	21 ms	9644 KB	Output is correct
6	Correct	19 ms	9164 KB	Output is correct
7	Correct	22 ms	9548 KB	Output is correct
8	Correct	157 ms	72364 KB	Output is correct
9	Correct	316 ms	125444 KB	Output is correct
10	Correct	349 ms	138820 KB	Output is correct
11	Correct	349 ms	149428 KB	Output is correct
12	Correct	392 ms	153984 KB	Output is correct
13	Correct	344 ms	188548 KB	Output is correct
14	Correct	344 ms	188684 KB	Output is correct
15	Runtime error	428 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-