제출 #1358599

#제출 시각아이디문제언어결과실행 시간메모리
1358599nxk02102010원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
149 ms69108 KiB
#include<bits/stdc++.h>
using namespace std;
/*
Idea:

*/
const int MAX= 1e9;
int q;
struct Segment{
        struct Node{
                int left;
                int right;
                int val;
                int lazy;
        };
        vector<Node> t;
        Segment (int q){
            t.reserve(2 * q * __lg(MAX));
        }
        int create(int l,int r){
                t.push_back({-1,-1,0,0});
                return (int)(t.size()) - 1;
        }
        void add(int v,int l,int r){
                t[v].val = r - l + 1;
                t[v].lazy = 1;
        }
        void pushdown(int v,int l,int r){
                if(t[v].lazy == 0 || l == r) return;
                int m = (l + r) >> 1;
                if(t[v].left == -1){
                        t[v].left = create(l,m);
                }
                if(t[v].right == -1){
                        t[v].right = create(m + 1,r);
                }
                add(t[v].left,l,m);
                add(t[v].right,m + 1,r);
                t[v].lazy = 0;
        }
        void update(int tl,int tr,int &v,int l,int r){
                if(l > tr || r < tl) return;
                if(v == -1) v = create(l,r);
                if(l >= tl && r <= tr){
                        add(v,l,r);
                        return;
                }
                if(t[v].lazy) pushdown(v,l,r);
                int m = (l + r) >> 1;
                update(tl,tr,t[v].left,l,m);
                update(tl,tr,t[v].right,m + 1,r);
                t[v].val = 0;
                if(t[v].left != -1) t[v].val += t[t[v].left].val;
                if(t[v].right != -1) t[v].val += t[t[v].right].val;
        }
        int get(int tl,int tr,int v,int l,int r){
                if(l > tr || r < tl) return 0;
                if(v == -1) return 0;
                if(l >= tl && r <= tr) return t[v].val;
                int m = (l + r) >> 1;
                pushdown(v,l,r);
                int left = 0,right = 0;
                if(t[v].left != -1) left = get(tl,tr,t[v].left,l,m);
                if(t[v].right != -1) right = get(tl,tr,t[v].right,m + 1,r);
                return left + right;
        }
};
int main(){
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        cin >> q;
        int c = 0;
        static Segment seg(q);
        int root = -1;
        while(q--){
                int type,l,r;cin >> type >> l >> r;
                if(type == 1){
                        cout << (c = seg.get(l + c,r + c,root,1,MAX)) << '\n';
                }
                else{
                        seg.update(l + c,r + c,root,1,MAX);
                }
        }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…