Submission #651872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651872	2022-10-20T11:24:59 Z	lite_27	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	186 ms	3020 KB

apple

#include <bits/stdc++.h>
using namespace std;
const int N = 1e9;
struct node
{
    int cnt;
    bool lz;
    node *left, *right;
    node() : cnt(0), lz(0), left(NULL), right(NULL) {}
};
node *root;
void propogate(node *v)
{
    if (v->lz)
    {
        if (!v->left)
            v->left = new node();
        v->left->lz = 1;
        if (!v->right)
            v->right = new node();
        v->right->lz = 1;
    }
}
void update(int l, int r, int tl = 0, int tr = N - 1, node *v = root)
{
    if (tr < l or r < tl)
    {
        if (v->lz)
            v->cnt = tr - tl + 1;
        propogate(v);
        return;
    }
    if (l <= tl and tr <= r)
    {
        v->cnt = tr - tl + 1;
        v->lz = 1;
        propogate(v);
        return;
    }
    if (v->lz)
        return;
    int mid = (tr + tl) >> 1;
    if (!v->left)
        v->left = new node();
    if (!v->right)
        v->right = new node();
    propogate(v);
    update(l, r, tl, mid, v->left);
    update(l, r, mid + 1, tr, v->right);
    v->cnt = v->left->cnt + v->right->cnt;
}
int query(int l, int r, int tl = 0, int tr = N - 1, node *v = root)
{
    if (tr < l or r < tl)
    {
        if (v->lz)
            v->cnt = tr - tl + 1;
        propogate(v);
        return 0;
    }
    if (l <= tl and tr <= r)
    {
        if (v->lz)
            v->cnt = tr - tl + 1;
        propogate(v);
        return v->cnt;
    }
    int mid = (tr + tl) >> 1;
    propogate(v);
    if (v->lz)
        return min(r, tr) - max(l, tl) + 1;
    int ans = (v->left ? query(l, r, tl, mid, v->left) : 0) + (v->right ? query(l, r, mid + 1, tr, v->right) : 0);
    v->cnt = (v->left ? v->left->cnt : 0) + (v->right ? v->right->cnt : 0);
    return ans;
}
int main()
{
    int m;
    cin >> m;
    int c = 0;
    int t, x, y;
    root = new node();
    while (m--)
    {
        cin >> t >> x >> y;
        x--, y--;
        if (t == 1)
        {
            c = query(c + x, c + y);
            cout << c << '\n';
        }
        else
        {
            update(c + x, c + y);
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	344 KB	Output is correct
5	Correct	29 ms	328 KB	Output is correct
6	Correct	18 ms	340 KB	Output is correct
7	Correct	23 ms	320 KB	Output is correct
8	Correct	78 ms	496 KB	Output is correct
9	Correct	156 ms	636 KB	Output is correct
10	Correct	151 ms	700 KB	Output is correct
11	Correct	173 ms	684 KB	Output is correct
12	Correct	171 ms	592 KB	Output is correct
13	Correct	177 ms	708 KB	Output is correct
14	Correct	186 ms	748 KB	Output is correct
15	Correct	166 ms	3020 KB	Output is correct
16	Correct	168 ms	2948 KB	Output is correct
17	Correct	171 ms	2844 KB	Output is correct
18	Correct	149 ms	2852 KB	Output is correct
19	Correct	166 ms	2976 KB	Output is correct
20	Correct	178 ms	3008 KB	Output is correct