Submission #547365

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547365	2022-04-10T14:14:46 Z	danikoynov	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	398 ms	200012 KB

apple

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxm = (1 << 17), maxn = 1e9;

struct node
{
    int sum, lazy, lf_bor, rf_bor, lf_id, rf_id;

    node()
    {
        sum = 0;
        lazy = 0;
        lf_bor = rf_bor = lf_id = rf_id = -1;
    }

    node(int _lf_bor, int _rf_bor)
    {
        sum = 0;
        lazy = 0;
        lf_bor = _lf_bor;
        rf_bor = _rf_bor;
        lf_id = rf_id = -1;
    }
};


node tree[maxm * 64];
int last_used;

void make_children(int root)
{
    if (tree[root].lf_bor == tree[root].rf_bor)
        return;
    int mid = (tree[root].lf_bor + tree[root].rf_bor) / 2;
    if (tree[root].lf_id == -1)
    {
        tree[root].lf_id = ++ last_used;
        tree[last_used] = node(tree[root].lf_bor, mid);
    }
    if (tree[root].rf_id == -1)
    {
        tree[root].rf_id = ++ last_used;
        tree[last_used] = node(mid + 1, tree[root].rf_bor);
    }
}

void push_lazy(int root)
{
    if (tree[root].lazy == 0)
        return;

    tree[root].sum = tree[root].rf_bor - tree[root].lf_bor + 1;
    if (tree[root].lf_bor != tree[root].rf_bor)
    {
        tree[tree[root].lf_id].lazy = 1;
        tree[tree[root].rf_id].lazy = 1;
    }

    tree[root].lazy = 0;
}

void update(int root, int qleft, int qright)
{
    make_children(root);
    push_lazy(root);

    if (tree[root].lf_bor > qright || tree[root].rf_bor < qleft)
        return;

    if (tree[root].lf_bor >= qleft && tree[root].rf_bor <= qright)
    {
        tree[root].lazy = 1;
        push_lazy(root);
        return;
    }

    update(tree[root].lf_id, qleft, qright);
    update(tree[root].rf_id, qleft, qright);

    tree[root].sum = tree[tree[root].lf_id].sum + tree[tree[root].rf_id].sum;
}

int query(int root, int qleft, int qright)
{
    make_children(root);
    push_lazy(root);

    if (tree[root].lf_bor > qright || tree[root].rf_bor < qleft)
        return 0;

    if (tree[root].lf_bor >= qleft && tree[root].rf_bor <= qright)
        return tree[root].sum;

    return query(tree[root].lf_id, qleft, qright) +
           query(tree[root].rf_id, qleft, qright);
}

int m, c;
void solve()
{
    cin >> m;
    tree[0] = node(1, maxn);
    for (int i = 1; i <= m; i ++)
    {
        int d, x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        if (d == 1)
        {
            int ans = query(0, x, y);
            cout << ans << endl;
            c = ans;
        }
        else
        {
            update(0, x, y);
        }
    }

}

int main()
{
    speed();
    solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	197364 KB	Output is correct
2	Correct	109 ms	197196 KB	Output is correct
3	Correct	94 ms	197376 KB	Output is correct
4	Correct	97 ms	197192 KB	Output is correct
5	Correct	101 ms	197524 KB	Output is correct
6	Correct	106 ms	197420 KB	Output is correct
7	Correct	103 ms	197424 KB	Output is correct
8	Correct	190 ms	198228 KB	Output is correct
9	Correct	328 ms	199304 KB	Output is correct
10	Correct	320 ms	199648 KB	Output is correct
11	Correct	334 ms	199464 KB	Output is correct
12	Correct	354 ms	199440 KB	Output is correct
13	Correct	299 ms	199776 KB	Output is correct
14	Correct	294 ms	199764 KB	Output is correct
15	Correct	392 ms	199932 KB	Output is correct
16	Correct	388 ms	199928 KB	Output is correct
17	Correct	315 ms	199836 KB	Output is correct
18	Correct	297 ms	199792 KB	Output is correct
19	Correct	392 ms	200012 KB	Output is correct
20	Correct	398 ms	199896 KB	Output is correct