답안 #616932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616932	2022-08-01T07:44:28 Z	Hanksburger	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	368 ms	123056 KB

apple

#include <bits/stdc++.h>
using namespace std;
int seg[10000005], lazy[10000005], tl[10000005], tr[10000005], cnt=1;
void push(int i, int l, int r)
{
    if (lazy[i])
    {
        lazy[i]=0;
        seg[i]=r-l+1;
        if (!tl[i])
            tl[i]=++cnt;
        if (!tr[i])
            tr[i]=++cnt;
        lazy[tl[i]]=lazy[tr[i]]=1;
    }
}
void update(int i, int l, int r, int ql, int qr)
{
    push(i, l, r);
    if (ql<=l && r<=qr)
    {
        lazy[i]=1;
        push(i, l, r);
        return;
    }
    if (!tl[i])
        tl[i]=++cnt;
    if (!tr[i])
        tr[i]=++cnt;
    int m=(l+r)/2;
    if (l<=qr && ql<=m)
        update(tl[i], l, m, ql, qr);
    if (m+1<=qr && ql<=r)
        update(tr[i], m+1, r, ql, qr);
    push(tl[i], l, m);
    push(tr[i], m+1, r);
    seg[i]=seg[tl[i]]+seg[tr[i]];
}
int query(int i, int l, int r, int ql, int qr)
{
    push(i, l, r);
    if (ql<=l && r<=qr)
        return seg[i];
    if (!tl[i])
        tl[i]=++cnt;
    if (!tr[i])
        tr[i]=++cnt;
    int m=(l+r)/2, ans=0;
    if (l<=qr && ql<=m)
        ans+=query(tl[i], l, m, ql, qr);
    if (m+1<=qr && ql<=r)
        ans+=query(tr[i], m+1, r, ql, qr);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, c=0;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        int d, x, y;
        cin >> d >> x >> y;
        if (d==1)
            cout << (c=query(1, 1, 1e9, x+c, y+c)) << '\n';
        else
            update(1, 1, 1e9, x+c, y+c);
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	10 ms	3156 KB	Output is correct
5	Correct	14 ms	3700 KB	Output is correct
6	Correct	14 ms	3592 KB	Output is correct
7	Correct	12 ms	3796 KB	Output is correct
8	Correct	120 ms	26060 KB	Output is correct
9	Correct	214 ms	45132 KB	Output is correct
10	Correct	226 ms	49676 KB	Output is correct
11	Correct	234 ms	53428 KB	Output is correct
12	Correct	259 ms	55048 KB	Output is correct
13	Correct	197 ms	63588 KB	Output is correct
14	Correct	205 ms	64296 KB	Output is correct
15	Correct	367 ms	117672 KB	Output is correct
16	Correct	368 ms	120180 KB	Output is correct
17	Correct	222 ms	68428 KB	Output is correct
18	Correct	199 ms	68452 KB	Output is correct
19	Correct	330 ms	122844 KB	Output is correct
20	Correct	303 ms	123056 KB	Output is correct