Submission #1221239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221239		Sofiatpc	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	339 ms	130708 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAX = 1e9;
vector<int> sum, lz, e, d;

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

void refresh(int node, int l, int r){
    if(lz[node] == 0)return;
    sum[node] = (r-l+1)*lz[node];
    if(l != r){
        if(e[node] == 0)e[node] = create();
        lz[ e[node] ] = lz[node];
        if(d[node] == 0)d[node] = create();
        lz[ d[node] ] = lz[node];
    }
    lz[node] = 0;
}

void update(int node, int l, int r, int i, int j){
    refresh(node,l,r);
    if(j < l || r < i)return;
    if(i <= l && r <= j){
        lz[node] = 1;
        refresh(node,l,r);
        return;
    }

    int mid = (l+r)>>1;
    if(e[node] == 0)e[node] = create();
    if(d[node] == 0)d[node] = create();
    update(e[node],l,mid,i,j); update(d[node],mid+1,r,i,j);

    sum[node] = sum[e[node]] + sum[d[node]];
}

int query(int node, int l, int r, int i, int j){
    if(node == 0)return 0;
    refresh(node,l,r);
    if(j < l || r < i)return 0;
    if(i <= l && r <= j)return sum[node];

    int mid = (l+r)>>1;
    return query(e[node],l,mid,i,j) + query(d[node],mid+1,r,i,j);
}

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

    int m; cin>>m;
    create(); create();
    int c = 0;
    for(int i = 1; i <= m; i++){
        int d,x,y; cin>>d>>x>>y;
        if(d == 1){
            c = query(1,1,MAX, x+c,y+c);
            cout<<c<<"\n";
        }else update(1,1,MAX, x+c,y+c);
    }
}

• Subtask 1: 100 / 100