Submission #651869

#	Time	Username	Problem	Language	Result	Execution time	Memory
651869		lite_27	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	695 ms	262144 KiB

apple

#include <bits/stdc++.h>
using namespace std;
const int N = 1e9;
struct node
{
    int cnt;
    int 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;
        v->lz = 0;
    }
}
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;
    }
    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);
    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: 0 / 100