답안 #531282

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

apple

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

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

const int64_t MAXN = 64 * 123456;
DSegTreeItem *nodes[MAXN];

class DynamicSegTree
{
  public:
    DynamicSegTree(int n)
    {
        this->size = n, this->last = 0;
        this->make_new();
    }
    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, last;
    DSegTreeItem *make_new()
    {
        DSegTreeItem *nx = new DSegTreeItem({0, 0, nullptr, nullptr});
        assert(last < MAXN);
        nodes[last] = nx;
        return nodes[last++];
    }
    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(1e10);

    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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	18 ms	10956 KB	Output is correct
5	Correct	22 ms	13268 KB	Output is correct
6	Correct	21 ms	12748 KB	Output is correct
7	Correct	22 ms	13224 KB	Output is correct
8	Correct	190 ms	102108 KB	Output is correct
9	Correct	362 ms	176776 KB	Output is correct
10	Correct	397 ms	195416 KB	Output is correct
11	Correct	395 ms	210428 KB	Output is correct
12	Correct	415 ms	216668 KB	Output is correct
13	Correct	364 ms	253636 KB	Output is correct
14	Correct	396 ms	256532 KB	Output is correct
15	Runtime error	329 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-