Submission #547365

#	Time	Username	Problem	Language	Result	Execution time	Memory
547365		danikoynov	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	398 ms	200012 KiB

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 / 100