Submission #739935

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739935	2023-05-11T17:17:06 Z	aykhn	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	317 ms	111196 KB

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.0 / 100.0

#	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	2856 KB	Output is correct
5	Correct	18 ms	3532 KB	Output is correct
6	Correct	18 ms	3284 KB	Output is correct
7	Correct	17 ms	3540 KB	Output is correct
8	Correct	118 ms	25968 KB	Output is correct
9	Correct	196 ms	38756 KB	Output is correct
10	Correct	220 ms	47408 KB	Output is correct
11	Correct	184 ms	40112 KB	Output is correct
12	Correct	215 ms	44892 KB	Output is correct
13	Correct	194 ms	43104 KB	Output is correct
14	Correct	197 ms	45644 KB	Output is correct
15	Correct	273 ms	86732 KB	Output is correct
16	Correct	317 ms	111196 KB	Output is correct
17	Correct	202 ms	52396 KB	Output is correct
18	Correct	201 ms	52312 KB	Output is correct
19	Correct	277 ms	96968 KB	Output is correct
20	Correct	286 ms	95392 KB	Output is correct