Submission #531284

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

apple

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

struct DSegTreeItem
{
    int32_t val, lazy;
    DSegTreeItem *l, *r;
};

const int64_t MAXN = 1e7 + 1;
DSegTreeItem *nodes[MAXN];

class DynamicSegTree
{
  public:
    DynamicSegTree(int n)
    {
        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;
    DSegTreeItem *make_new()
    {
        DSegTreeItem *nx = new DSegTreeItem({0, 0, nullptr, nullptr});
        assert(last < MAXN);
        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	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	23 ms	8012 KB	Output is correct
5	Correct	22 ms	9548 KB	Output is correct
6	Correct	23 ms	9160 KB	Output is correct
7	Correct	30 ms	9548 KB	Output is correct
8	Correct	182 ms	73000 KB	Output is correct
9	Correct	349 ms	126344 KB	Output is correct
10	Correct	380 ms	139744 KB	Output is correct
11	Correct	369 ms	150492 KB	Output is correct
12	Correct	356 ms	155052 KB	Output is correct
13	Correct	371 ms	179972 KB	Output is correct
14	Correct	343 ms	181824 KB	Output is correct
15	Runtime error	442 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-