제출 #676540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676540		KindaNameless	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	405 ms	200148 KiB

apple

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

struct node{
    int val, lazy, tl, tr, lc, rc;

    node(int _l, int _r){
        val = 0; lazy = 0; tl = _l; tr = _r; lc = -1; rc = -1;
    }

    void oper(int add){
        if(!add)return;
        val = tr - tl + 1;
        lazy = add;
    }
};

struct segment_tree{
    vector<node> seg;

    segment_tree(){
        seg.emplace_back(node(1, 1e9));
    }

    inline int comb(int a, int b){
        return a + b;
    }

    inline void pull(int ind){
        seg[ind].val = comb(seg[seg[ind].lc].val, seg[seg[ind].rc].val);
    }

    void prop(int ind){
        if(seg[ind].tl != seg[ind].tr){
            seg[ind].oper(seg[ind].lazy);
            int m = (seg[ind].tl + seg[ind].tr) / 2;
            if(seg[ind].lc == -1){
                seg[ind].lc = (int)seg.size();
                seg.emplace_back(node(seg[ind].tl, m));
            }
            if(seg[ind].rc == -1){
                seg[ind].rc = (int)seg.size();
                seg.emplace_back(node(m+1, seg[ind].tr));
            }
            seg[seg[ind].lc].oper(seg[ind].lazy);
            seg[seg[ind].rc].oper(seg[ind].lazy);
            seg[ind].lazy = 0;
        }
    }

    void upd(int l, int r, int ind = 0){
        if(l > seg[ind].tr || r < seg[ind].tl){
            return;
        }
        if(l <= seg[ind].tl && seg[ind].tr <= r){
            seg[ind].oper(1);
            return;
        }
        prop(ind);
        upd(l, r, seg[ind].lc);
        upd(l, r, seg[ind].rc);
        pull(ind);
    }

    int query(int l, int r, int ind = 0){
        if(l > seg[ind].tr || r < seg[ind].tl){
            return 0;
        }
        if(l <= seg[ind].tl && seg[ind].tr <= r){
            seg[ind].oper(seg[ind].lazy);
            return seg[ind].val;
        }
        prop(ind);
        return comb(query(l, r, seg[ind].lc),
                    query(l, r, seg[ind].rc));
    }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    segment_tree ST;

    int M; cin >> M;

    int c = 0;
    for(int i = 1; i <= M; ++i){
        int d, x, y; cin >> d >> x >> y;
        if(d == 1){
            c = ST.query(x + c, y + c);
            cout << c << "\n";
        }
        else{
            ST.upd(x + c, y + c);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100