Submission #531280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531280	2022-02-28T10:48:39 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	408 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(1e7 + 1);
        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	29 ms	78540 KB	Output is correct
2	Correct	30 ms	78556 KB	Output is correct
3	Correct	28 ms	78556 KB	Output is correct
4	Correct	50 ms	87780 KB	Output is correct
5	Correct	49 ms	89616 KB	Output is correct
6	Correct	47 ms	89200 KB	Output is correct
7	Correct	48 ms	89668 KB	Output is correct
8	Correct	192 ms	165892 KB	Output is correct
9	Correct	366 ms	229840 KB	Output is correct
10	Correct	400 ms	245852 KB	Output is correct
11	Correct	400 ms	258756 KB	Output is correct
12	Runtime error	408 ms	262148 KB	Execution killed with signal 9
13	Halted	0 ms	0 KB	-