Submission #1089497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089497		BLOBVISGOD	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	241 ms	106324 KiB

apple

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 1e5+10;

struct node{
    int sm, lazy, l, r, lc, rc;
    int val(){
        return lazy?(r-l):sm;
    }
};

int n = 1;
node seg[81*N];

void ensure(int id){
    auto& v = seg[id];
    int mid = (v.l+v.r)/2;
    if (v.lc<0){
        seg[n] = {0,v.lazy,v.l,mid,-1,-1};
        v.lc = n++;
    }if (v.rc<0){
        seg[n] = {0,v.lazy,mid,v.r,-1,-1};
        v.rc = n++;
    }
}

void push(int id){
    ensure(id);
    auto& v = seg[id];
    if (v.lazy) seg[v.lc].lazy = v.lazy, seg[v.rc].lazy = v.lazy;
    v.sm = v.val();
    v.lazy = 0;
}

void pull(int id){
    auto& v = seg[id];
    v.sm = seg[v.lc].val() + seg[v.rc].val();
}

void ud(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return;
    if (v.l >= ql and v.r <= qr){
        seg[i].lazy = 1;
        return;
    }
    push(i);
    ud(v.lc,ql,qr), ud(v.rc,ql,qr);
    pull(i);
}

void update(int l, int r) {
    ud(0,l,r);
}

int gt(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return 0;
    if (v.l >= ql and v.r <= qr) 
        return v.val();
    push(i);
    return gt(v.lc,ql,qr) + gt(v.rc,ql,qr);
}

int get(int l, int r){
    return gt(0,l,r);
}


int main(){
    seg[0] = {0,0,0,1<<30,-1,-1};

    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int m, last = 0; cin >> m;

    while(m--){
        int t,x,y; cin >> t >> x >> y;
        x += last, y += last;
        if (t==1){
            last = get(x,y+1);
            cout << last << '\n';
        }else{
            update(x,y+1);
        }
    }

}

• Subtask 1: 100 / 100