답안 #531310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531310	2022-02-28T11:29:57 Z	dreadarceus	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	403 ms	262148 KB

apple

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

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

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 = new DSegTreeItem({0, 0, nullptr, nullptr});
        nodes[last++] = nw;
        return nw;
    }
    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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	17 ms	7244 KB	Output is correct
5	Correct	19 ms	8700 KB	Output is correct
6	Correct	19 ms	8380 KB	Output is correct
7	Correct	19 ms	8612 KB	Output is correct
8	Correct	141 ms	64144 KB	Output is correct
9	Correct	293 ms	109132 KB	Output is correct
10	Correct	302 ms	122400 KB	Output is correct
11	Correct	312 ms	132908 KB	Output is correct
12	Correct	322 ms	137412 KB	Output is correct
13	Correct	302 ms	170952 KB	Output is correct
14	Correct	304 ms	173048 KB	Output is correct
15	Runtime error	403 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-