Submission #915371

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915371	2024-01-23T18:53:26 Z	codefox	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	323 ms	199872 KB

apple

#include<bits/stdc++.h>

using namespace std;

#define int long long

int N = 1<<30;
int M = 1<<23;
vector<array<int, 2>> down(M, {-1, -1});
int c = 1;
vector<int> bit(M, 0);

void update(int curr, int l, int r, int cl, int cr)
{
    if (cr < l || cl > r) return;
    if (l <= cl && cr <= r) 
    {
        bit[curr] = cr-cl+1;
        return;
    }
    if (down[curr][1]==-1)
    {
        down[curr][0] = ++c;
        down[curr][1] = ++c;
    }
    int subl = down[curr][0];
    int subr = down[curr][1];

    if(bit[curr] == cr-cl+1)
    {
        bit[subl] = (cr-cl+1)/2;
        bit[subr]=(cr-cl+1)/2;
    }
    int m = (cl+cr)/2;
    update(subl, l, r, cl, m);
    update(subr, l, r, m+1, cr);
    bit[curr] = bit[subl]+bit[subr];
    return;
}

int query(int curr, int l, int r, int cl, int cr)
{
    if (cr < l || cl > r) return 0;
    if (l <= cl && cr <= r)  return bit[curr];
    if (down[curr][1]==-1)
    {
        down[curr][0] = ++c;
        down[curr][1] = ++c;
    }
    int subl = down[curr][0];
    int subr = down[curr][1];

    if(bit[curr] == cr-cl+1)
    {
        bit[subl] = (cr-cl+1)/2;
        bit[subr]=(cr-cl+1)/2;
    }
    int m = (cl+cr)/2;
    int sol = 0;
    sol += query(subl, l, r, cl, m);
    sol += query(subr, l, r, m+1, cr);
    return sol;
}

int32_t main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    int q;
    cin >> q;
    int last = 0;
    for (int i = 0; i < q; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        b--; c--;
        b+=last;
        c+=last;
        if (a==2)
        {
            update(1, b, c, 0, N-1);
        }
        else
        {
            last = query(1, b, c, 0, N-1);
            cout << last << "\n";
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	197356 KB	Output is correct
2	Correct	49 ms	197208 KB	Output is correct
3	Correct	48 ms	197396 KB	Output is correct
4	Correct	60 ms	197460 KB	Output is correct
5	Correct	62 ms	197456 KB	Output is correct
6	Correct	64 ms	197520 KB	Output is correct
7	Correct	62 ms	197456 KB	Output is correct
8	Correct	150 ms	198380 KB	Output is correct
9	Correct	282 ms	198916 KB	Output is correct
10	Correct	277 ms	198768 KB	Output is correct
11	Correct	277 ms	198804 KB	Output is correct
12	Correct	271 ms	198736 KB	Output is correct
13	Correct	262 ms	199356 KB	Output is correct
14	Correct	259 ms	199044 KB	Output is correct
15	Correct	319 ms	199336 KB	Output is correct
16	Correct	315 ms	198996 KB	Output is correct
17	Correct	259 ms	199312 KB	Output is correct
18	Correct	261 ms	199072 KB	Output is correct
19	Correct	323 ms	199052 KB	Output is correct
20	Correct	306 ms	199872 KB	Output is correct