제출 #1267487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267487		nathlol2	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	205 ms	110128 KiB

apple

#include <bits/stdc++.h>
using namespace std;
struct sparseseg{
    struct node{
        int sm, lazy;
        node *l, *r;
        node(int sm): sm(sm), lazy(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt = nullptr;
    void push(pnode &k, int l, int r){
        if(k && k->lazy != 0){
            k->sm = r - l + 1;
            if(l != r){
                if(!k->l) k->l = new node(0);
                if(!k->r) k->r = new node(0);
                k->l->lazy = 1;
                k->r->lazy = 1;
            }
            k->lazy = 0;
        }
    }
    void upd(int l, int r, int L, int R, pnode &k){
        if(r < L || l > R) return;
        if(k && k->sm == r - l + 1) return;
        if(!k) k = new node(0);
        push(k, l, r);
        if(l >= L && r <= R) return k->lazy = 1, push(k, l, r), void();
        int md = l + (r - l) / 2;
        upd(l, md, L, R, k->l);
        upd(md + 1, r, L, R, k->r);
        k->sm = (k->l ? k->l->sm : 0) + (k->r ? k->r->sm : 0);
    }
    int qry(int l, int r, int L, int R, pnode k){
        if(r < L || l > R || !k) return 0;
        push(k, l, r);
        if(L <= l && r <= R) return k->sm;
        int md = l + (r - l) / 2;
        return qry(l, md, L, R, k->l) + qry(md + 1, r, L, R, k->r);
    }
}s;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q, c = 0;
    cin >> q;
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1){
            int ans = s.qry(1, 1e9, l + c, r + c, s.rt);
            cout << ans << '\n';
            c = ans;
        }else{
            s.upd(1, 1e9, l + c, r + c, s.rt);
        }
    }
}

• Subtask 1: 100 / 100