답안 #920650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920650 2024-02-02T20:28:15 Z Irate 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
291 ms 170064 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 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 11 ms 14016 KB Output is correct
5 Correct 13 ms 17240 KB Output is correct
6 Correct 13 ms 17244 KB Output is correct
7 Correct 14 ms 17416 KB Output is correct
8 Correct 87 ms 85076 KB Output is correct
9 Correct 187 ms 170064 KB Output is correct
10 Correct 179 ms 169824 KB Output is correct
11 Correct 218 ms 169824 KB Output is correct
12 Correct 222 ms 169808 KB Output is correct
13 Correct 171 ms 169856 KB Output is correct
14 Correct 173 ms 169984 KB Output is correct
15 Correct 291 ms 169928 KB Output is correct
16 Correct 253 ms 169812 KB Output is correct
17 Correct 171 ms 169812 KB Output is correct
18 Correct 177 ms 169804 KB Output is correct
19 Correct 258 ms 169808 KB Output is correct
20 Correct 268 ms 169856 KB Output is correct