답안 #915367

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
915367 2024-01-23T18:50:12 Z codefox 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
378 ms 202928 KB
#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;
}
# 결과 실행 시간 메모리 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 -