Submission #531281

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531281	2022-02-28T10:49:43 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	422 ms	262148 KB

apple

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

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

  public:
    DynamicSegTree(int n)
    {
        this->nodes.resize(64 * 123456);
        this->size = n;
        this->last = 0;
        this->make_new();
    }
    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, last;
    vector<DSegTreeItem *> nodes;
    DSegTreeItem *make_new()
    {
        DSegTreeItem *nx = new DSegTreeItem({0, 0, nullptr, nullptr});
        assert(last < (int)nodes.size());
        nodes[last] = nx;
        return nodes[last++];
    }
    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(1e10);

    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	30 ms	62156 KB	Output is correct
2	Correct	24 ms	62084 KB	Output is correct
3	Correct	29 ms	62160 KB	Output is correct
4	Correct	40 ms	71284 KB	Output is correct
5	Correct	43 ms	73264 KB	Output is correct
6	Correct	42 ms	72812 KB	Output is correct
7	Correct	44 ms	73184 KB	Output is correct
8	Correct	210 ms	149456 KB	Output is correct
9	Correct	380 ms	213408 KB	Output is correct
10	Correct	405 ms	229496 KB	Output is correct
11	Correct	407 ms	242372 KB	Output is correct
12	Correct	422 ms	248116 KB	Output is correct
13	Runtime error	340 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-