답안 #531312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531312	2022-02-28T11:32:13 Z	dreadarceus	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	466 ms	262144 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 = 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

#	결과	실행 시간	메모리	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	10 ms	4436 KB	Output is correct
5	Correct	12 ms	5324 KB	Output is correct
6	Correct	12 ms	5068 KB	Output is correct
7	Correct	12 ms	5292 KB	Output is correct
8	Correct	97 ms	38720 KB	Output is correct
9	Correct	210 ms	65832 KB	Output is correct
10	Correct	212 ms	73676 KB	Output is correct
11	Correct	218 ms	80032 KB	Output is correct
12	Correct	225 ms	82664 KB	Output is correct
13	Correct	206 ms	102852 KB	Output is correct
14	Correct	198 ms	104048 KB	Output is correct
15	Runtime error	466 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-