Submission #616932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
616932	2022-08-01T07:44:28 Z	Hanksburger	Monkey and Apple-trees (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

#	Verdict	Execution time	Memory	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