답안 #412180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
412180 2021-05-26T15:16:43 Z ruadhan 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
592 ms 161084 KB
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct Node
{
    int sum, lazy, tl, tr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

const int MX = 1e5+5;
Node segtree[4*17*MX];
int M;
int cnt = 2;

void push_lazy(int node)
{
    if (segtree[node].lazy)
    {
        segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1)
        {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1)
        {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }
        segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
        segtree[node].lazy = 0;
    }
}

void update(int node, int l, int r)
{
    if (l == segtree[node].tl && r == segtree[node].tr)
    {
        segtree[node].lazy = 1;
        push_lazy(node);
    }
    else
    {
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1)
        {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1)
        {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }

        if (l > mid)
            update(segtree[node].r, l, r);
        else if (r <= mid)
            update(segtree[node].l, l, r);
        else
        {
            update(segtree[node].l, l, mid);
            update(segtree[node].r, mid + 1, r);
        }

        push_lazy(segtree[node].l);
        push_lazy(segtree[node].r);
        segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
    }
}

int query(int node, int l, int r)
{
    push_lazy(node);
    if (l == segtree[node].tl && r == segtree[node].tr)
        return segtree[node].sum;
    else
    {
        int mid = (segtree[node].tl + segtree[node].tr) / 2;
        if (segtree[node].l == -1)
        {
            segtree[node].l = cnt++;
            segtree[segtree[node].l].tl = segtree[node].tl;
            segtree[segtree[node].l].tr = mid;
        }
        if (segtree[node].r == -1)
        {
            segtree[node].r = cnt++;
            segtree[segtree[node].r].tl = mid + 1;
            segtree[segtree[node].r].tr = segtree[node].tr;
        }

        if (l > mid)
            return query(segtree[node].r, l, r);
        else if (r <= mid)
            return query(segtree[node].l, l, r);
        else
            return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
    }
}

int main()
{
    cin >> M;

    segtree[1].sum = 0, segtree[1].lazy = 0;
    segtree[1].tl = 1, segtree[1].tr = 1e9;

    int D, X, Y, C = 0;
    while (M--)
    {
        cin >> D >> X >> Y;
        X += C, Y += C;
        if (D == 1)
        {
            C = query(1, X, Y);
            cout << C << '\n';
        }
        else
        {
            update(1, X, Y);
        }
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 159940 KB Output is correct
2 Correct 77 ms 159972 KB Output is correct
3 Correct 74 ms 159948 KB Output is correct
4 Correct 99 ms 159932 KB Output is correct
5 Correct 106 ms 160000 KB Output is correct
6 Correct 110 ms 160048 KB Output is correct
7 Correct 107 ms 159936 KB Output is correct
8 Correct 267 ms 160040 KB Output is correct
9 Correct 498 ms 161084 KB Output is correct
10 Correct 506 ms 160740 KB Output is correct
11 Correct 508 ms 160840 KB Output is correct
12 Correct 517 ms 160724 KB Output is correct
13 Correct 465 ms 160824 KB Output is correct
14 Correct 476 ms 160960 KB Output is correct
15 Correct 592 ms 160708 KB Output is correct
16 Correct 566 ms 160708 KB Output is correct
17 Correct 469 ms 160632 KB Output is correct
18 Correct 471 ms 160680 KB Output is correct
19 Correct 569 ms 160628 KB Output is correct
20 Correct 568 ms 160708 KB Output is correct