답안 #531288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531288	2022-02-28T10:57:39 Z	dreadarceus	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	450 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(1e7);
        this->make_new();
        this->size = n;
    }
    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;
    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 = 1;
            cur->r->lazy = 1;
        }
        cur->val = r - l;
        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);
    }
}

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	1 ms	204 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	17 ms	7904 KB	Output is correct
5	Correct	20 ms	9512 KB	Output is correct
6	Correct	20 ms	9244 KB	Output is correct
7	Correct	19 ms	9460 KB	Output is correct
8	Correct	162 ms	72464 KB	Output is correct
9	Correct	326 ms	125440 KB	Output is correct
10	Correct	350 ms	138820 KB	Output is correct
11	Correct	399 ms	149360 KB	Output is correct
12	Correct	381 ms	153924 KB	Output is correct
13	Correct	334 ms	179348 KB	Output is correct
14	Correct	339 ms	181316 KB	Output is correct
15	Runtime error	450 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-