Submission #531314

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

apple

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

struct DSegTreeItem
{
    int val;
    bool lazy;
    DSegTreeItem *l, *r;
};
const int mx = 64 * 123456;
DSegTreeItem nodes[mx];

class DynamicSegTree
{
  public:
    DynamicSegTree(int n)
    {
        this->size = n, last = 0;
        this->make_new();
    }
    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, last;
    DSegTreeItem *make_new()
    {
        DSegTreeItem nw = DSegTreeItem({0, 0, nullptr, nullptr});
        nodes[last++] = nw;
        return &nodes[last - 1];
    }
    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	0 ms	204 KB	Output is correct
4	Correct	11 ms	4440 KB	Output is correct
5	Correct	13 ms	5352 KB	Output is correct
6	Correct	12 ms	5196 KB	Output is correct
7	Correct	12 ms	5340 KB	Output is correct
8	Correct	98 ms	38676 KB	Output is correct
9	Correct	227 ms	65820 KB	Output is correct
10	Correct	243 ms	73712 KB	Output is correct
11	Correct	238 ms	80044 KB	Output is correct
12	Correct	244 ms	82724 KB	Output is correct
13	Correct	195 ms	102852 KB	Output is correct
14	Correct	195 ms	104004 KB	Output is correct
15	Runtime error	464 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-