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
#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);
        }
    }
}
# 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