답안 #531297

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

apple

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

class DynamicSegTree
{
    struct DSegTreeItem
    {
        int val;
        bool lazy;
        DSegTreeItem *l, *r;
    };

  public:
    DynamicSegTree(int n)
    {
        this->nodes.reserve(18 * 1e5);
        this->make_new();
        this->size = n;
    }
    void rangeUpdate(int x, int y, int v, 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 = v;
            propagateLazy(cur, l, r);
            return;
        }
        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)
    {
        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, 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;
    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 = 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	0 ms	328 KB	Output is correct
4	Correct	16 ms	7884 KB	Output is correct
5	Correct	22 ms	9548 KB	Output is correct
6	Correct	19 ms	9164 KB	Output is correct
7	Correct	21 ms	9460 KB	Output is correct
8	Correct	176 ms	85084 KB	Output is correct
9	Correct	347 ms	125412 KB	Output is correct
10	Correct	348 ms	138996 KB	Output is correct
11	Correct	369 ms	169664 KB	Output is correct
12	Correct	379 ms	169660 KB	Output is correct
13	Correct	346 ms	179444 KB	Output is correct
14	Correct	373 ms	181316 KB	Output is correct
15	Runtime error	448 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-