Submission #531269

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531269	2022-02-28T10:02:38 Z	dreadarceus	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	432 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->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	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	20 ms	11120 KB	Output is correct
5	Correct	23 ms	13372 KB	Output is correct
6	Correct	22 ms	12900 KB	Output is correct
7	Correct	23 ms	13384 KB	Output is correct
8	Correct	177 ms	101876 KB	Output is correct
9	Correct	374 ms	176000 KB	Output is correct
10	Correct	370 ms	194784 KB	Output is correct
11	Correct	432 ms	209368 KB	Output is correct
12	Correct	403 ms	215652 KB	Output is correct
13	Runtime error	352 ms	262148 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-