답안 #920649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920649 2024-02-02T20:26:45 Z vjudge1 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
306 ms 172296 KB
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
    vector<int>sTree, L, R;
    int nxt = 2;
    SegmentTree(int n){
        sTree.resize(144 * n);
        L.resize(144 * n);
        R.resize(144 * n);
    }
    void Propagate(int node, int l, int r){
        if(sTree[node] != r - l + 1)return;
        if(l != r){
            if(L[node] == 0)L[node] = nxt++;
            if(R[node] == 0)R[node] = nxt++;
            int mid = (l + r) >> 1;
            sTree[L[node]] = mid - l + 1;
            sTree[R[node]] = r - mid;
        }
    }
    void R_Update(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            sTree[node] = r - l + 1;
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr)return;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        R_Update(L[node], l, mid, ql, qr);
        R_Update(R[node], mid + 1, r, ql, qr);
        sTree[node] = sTree[L[node]] + sTree[R[node]];
    }
    int Query(int node, int l, int r, int ql, int qr){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            return sTree[node];
        }
        if(ql > r || l > qr)return 0;
        int mid = (l + r) >> 1;
        if(L[node] == 0)L[node] = nxt++;
        if(R[node] == 0)R[node] = nxt++;
        int lc = Query(L[node], l, mid, ql, qr);
        int rc = Query(R[node], mid + 1, r, ql, qr);
        return lc + rc;
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q, c = 0;
    cin >> q;
    SegmentTree tree(q);
    int n = 1e9;
    while(q--){
        int type, l, r;
        cin >> type >> l >> r;
        l += c;
        r += c;
        if(type == 1){
            c = tree.Query(1, 1, n, l, r);
            cout << c << '\n';
        }
        else{
            tree.R_Update(1, 1, n, l, r);
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 11 ms 14132 KB Output is correct
5 Correct 15 ms 17364 KB Output is correct
6 Correct 13 ms 17496 KB Output is correct
7 Correct 13 ms 17500 KB Output is correct
8 Correct 96 ms 85960 KB Output is correct
9 Correct 212 ms 171420 KB Output is correct
10 Correct 216 ms 171632 KB Output is correct
11 Correct 205 ms 171596 KB Output is correct
12 Correct 204 ms 171600 KB Output is correct
13 Correct 171 ms 171972 KB Output is correct
14 Correct 174 ms 171976 KB Output is correct
15 Correct 265 ms 172164 KB Output is correct
16 Correct 306 ms 172088 KB Output is correct
17 Correct 173 ms 171860 KB Output is correct
18 Correct 176 ms 171856 KB Output is correct
19 Correct 263 ms 172296 KB Output is correct
20 Correct 271 ms 172116 KB Output is correct