Submission #1308069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308069		harryleee	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	485 ms	260628 KiB

apple

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 1e9+10;

vector<int> seg, lz, e, d;

int create(){
    seg.push_back(0);
    lz.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return seg.size()-1;
}

void refresh(int pos, int ini, int fim){
    if(lz[pos]==0) return;
    seg[pos] = fim-ini+1;
    if(ini<fim){
        if(e[pos]==0){ int aux = create(); e[pos] = aux; }
        if(d[pos]==0){ int aux = create(); d[pos] = aux; }
        lz[e[pos]] = lz[d[pos]] = 1;
    }
    lz[pos] = 0;
}

void update(int pos, int ini, int fim, int l, int r){
    refresh(pos, ini, fim);
    if(fim<l || r<ini) return;
    if(l<=ini && fim<=r){
        lz[pos] = 1;
        refresh(pos, ini, fim);
        return;
    }
    int m = (ini+fim)>>1;
    if(e[pos]==0){ int aux = create(); e[pos] = aux; }
    if(d[pos]==0){ int aux = create(); d[pos] = aux; }
    update(e[pos], ini, m, l, r);
    update(d[pos], m+1, fim, l, r);
    seg[pos] = seg[e[pos]] + seg[d[pos]];
}

int query(int pos, int ini, int fim, int l, int r){
    refresh(pos, ini, fim);
    if(fim<l || r<ini) return 0;
    if(l<=ini && fim<=r) return seg[pos];
    int m = (ini+fim)>>1;
    if(e[pos]==0){ int aux = create(); e[pos] = aux; }
    if(d[pos]==0){ int aux = create(); d[pos] = aux; }
    return query(e[pos], ini, m, l, r) + query(d[pos], m+1, fim, l, r);
}

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

    create(); create();

    int q; cin >> q;
    int c = 0;
    while(q--){
        int op, l, r; cin >> op >> l >> r;
        if(op==2) update(1, 1, MAXN, l+c, r+c);
        else{
            c = query(1, 1, MAXN, l+c, r+c);
            cout << c << "\n";
        }
    }
}

• Subtask 1: 100 / 100