답안 #531314

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

apple

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

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

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	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	11 ms	4440 KB	Output is correct
5	Correct	13 ms	5352 KB	Output is correct
6	Correct	12 ms	5196 KB	Output is correct
7	Correct	12 ms	5340 KB	Output is correct
8	Correct	98 ms	38676 KB	Output is correct
9	Correct	227 ms	65820 KB	Output is correct
10	Correct	243 ms	73712 KB	Output is correct
11	Correct	238 ms	80044 KB	Output is correct
12	Correct	244 ms	82724 KB	Output is correct
13	Correct	195 ms	102852 KB	Output is correct
14	Correct	195 ms	104004 KB	Output is correct
15	Runtime error	464 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-