Submission #739935

#	Time	Username	Problem	Language	Result	Execution time	Memory
739935		aykhn	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	317 ms	111196 KiB

apple

#include <bits/stdc++.h>


/*
    author: aykhn
    5/1/2023
*/

using namespace std;

typedef long long ll;

const int oo = INT_MAX;
const ll ooo = LONG_MAX;
const ll mod = 1e9 + 7;

#define OPT ios_base::sync_with_stdio(0); \
            cin.tie(0); \
            cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pss pair<long,long>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;

struct Node
{
    int data = 0;
    bool done = true;
    Node *left = nullptr;
    Node *right = nullptr;
};

int c = 0;
int sz = 1;

void sett(int lx, int rx, int l, int r, Node *ptr)
{
    if (l >= rx || r <= lx) return;

    if (l >= lx && r <= rx)
    {
        ptr -> data = r - l;
        ptr -> done = 0;
        return;
    }

    int mid = (l + r) >> 1;

    if (ptr -> left == nullptr) ptr -> left = new Node;
    sett(lx, rx, l, mid, ptr -> left);
    if (ptr -> right == nullptr) ptr -> right = new Node;
    sett(lx, rx, mid, r, ptr -> right);

    if (ptr -> done == 0 && ptr -> data > 0)
    {
        sett(l, mid, l, mid, ptr -> left);
        sett(mid, r, mid, r, ptr -> right);
    }

    ptr -> data = ptr -> left -> data + ptr -> right -> data;
}

int get(int lx, int rx, int l, int r, Node *ptr)
{
    if (l >= rx || r <= lx) return 0;

    if (l >= lx && r <= rx)
    {
        return ptr -> data;
    }
    if (lx >= l && rx <= r && ptr -> data == r - l) return rx - lx;
    int mid = (l + r) >> 1;

    if (ptr -> done == 0 && ptr -> data > 0)
    {
        if (ptr -> left == nullptr) ptr -> left = new Node;
        sett(l, mid, l, mid, ptr -> left);
        if (ptr -> right == nullptr) ptr -> right= new Node;
        sett(mid, r, mid, r, ptr -> right);
    }

    int a, b;
    a = b = 0;

    if (ptr -> left != nullptr) a = get(lx, rx, l, mid, ptr -> left);
    if (ptr -> right != nullptr) b = get(lx, rx, mid, r, ptr -> right);


    return a + b;
}

int main()
{
    OPT;
    int m;
    cin >> m;

    Node *root = new Node;
    while (sz < 1000000000) sz <<= 1;

    while (m--)
    {
        int x, l, r;
        cin >> x >> l >> r;

        if (x == 2) sett(l - 1 + c, r + c, 0, sz, root);
        else
        {
            int x = get(l - 1 + c, r + c, 0, sz, root);
            cout << x << endl;
            c = x;
        }
    }
}

• Subtask 1: 100 / 100