Submission #967819

#	Time	Username	Problem	Language	Result	Execution time	Memory
967819		irmuun	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2476 ms	262144 KiB

apple

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll N=6e6;

struct Node{
    int sum,lazy,tl,tr,l,r;
    Node() : sum(0), lazy(0), l(-1), r(-1){}
};

Node sg[N];

int cnt=2;

void push(int node){
    if(sg[node].lazy==1){
        sg[node].sum=sg[node].tr-sg[node].tl+1;
        int mid=(sg[node].tl+sg[node].tr)/2;
        if(sg[node].l==-1){
            sg[node].l=cnt++;
            sg[sg[node].l].tl=sg[node].tl;
            sg[sg[node].l].tr=mid;
        }
        if(sg[node].r==-1){
            sg[node].r=cnt++;
            sg[sg[node].r].tl=mid+1;
            sg[sg[node].r].tr=sg[node].tr;
        }
        sg[sg[node].l].lazy=1;
        sg[sg[node].r].lazy=1;
        sg[node].lazy=0;
    }
}

int query(int node,int l,int r){
    push(node);
    if(sg[node].tl==l&&sg[node].tr==r){
        return sg[node].sum;
    }
    int mid=(sg[node].tl+sg[node].tr)/2;
    if(sg[node].l==-1){
        sg[node].l=cnt++;
        sg[sg[node].l].tl=sg[node].tl;
        sg[sg[node].l].tr=mid;
    }
    if(sg[node].r==-1){
        sg[node].r=cnt++;
        sg[sg[node].r].tl=mid+1;
        sg[sg[node].r].tr=sg[node].tr;
    }
    if(r<=mid){
        return query(sg[node].l,l,r);
    }
    if(l>mid){
        return query(sg[node].r,l,r);
    }
    return query(sg[node].l,l,mid)+query(sg[node].r,mid+1,r);
}

void update(int node,int l,int r){
    push(node);
    if(sg[node].tl==l&&sg[node].tr==r){
        sg[node].lazy=1;
        push(node);
        return;
    }
    int mid=(sg[node].tl+sg[node].tr)/2;
    if(sg[node].l==-1){
        sg[node].l=cnt++;
        sg[sg[node].l].tl=sg[node].tl;
        sg[sg[node].l].tr=mid;
    }
    if(sg[node].r==-1){
        sg[node].r=cnt++;
        sg[sg[node].r].tl=mid+1;
        sg[sg[node].r].tr=sg[node].tr;
    }
    if(r<=mid){
        update(sg[node].l,l,r);
    }
    else if(l>mid){
        update(sg[node].r,l,r);
    }
    else{
        update(sg[node].l,l,mid);
        update(sg[node].r,mid+1,r);
    }
    push(sg[node].l);
    push(sg[node].r);
    sg[node].sum=sg[sg[node].l].sum+sg[sg[node].r].sum;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin>>m;
    sg[1].sum=0;
    sg[1].lazy=0;
    sg[1].tl=1;
    sg[1].tr=1e9;
    int c=0;
    while(m--){
        int t,x,y;
        cin>>t>>x>>y;
        if(t==1){
            c=query(1,x+c,y+c);
            cout<<c<<"\n";
        }
        else{
            update(1,x+c,y+c);
        }
    }
}

• Subtask 1: 0 / 100