Submission #915367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915367	2024-01-23T18:50:12 Z	codefox	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	378 ms	202928 KB

apple

#include<bits/stdc++.h>

using namespace std;

#define int long long

int N = 1<<30;
int M = 1<<22;
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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	98904 KB	Output is correct
2	Correct	19 ms	98908 KB	Output is correct
3	Correct	18 ms	98740 KB	Output is correct
4	Correct	32 ms	98908 KB	Output is correct
5	Correct	36 ms	98908 KB	Output is correct
6	Correct	35 ms	99152 KB	Output is correct
7	Correct	36 ms	98904 KB	Output is correct
8	Correct	125 ms	99152 KB	Output is correct
9	Correct	271 ms	99156 KB	Output is correct
10	Correct	239 ms	100900 KB	Output is correct
11	Correct	265 ms	100940 KB	Output is correct
12	Correct	249 ms	100888 KB	Output is correct
13	Correct	269 ms	101456 KB	Output is correct
14	Correct	241 ms	101456 KB	Output is correct
15	Correct	294 ms	101392 KB	Output is correct
16	Correct	295 ms	101628 KB	Output is correct
17	Correct	228 ms	101412 KB	Output is correct
18	Correct	222 ms	101464 KB	Output is correct
19	Runtime error	378 ms	202928 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-