Submission #1116549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116549		Petrix	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	204 ms	97096 KiB

apple

#include <iostream>
using namespace std;

#define int long long

int cnt;
struct node{
    int sum,mar,lazy,lnod,rnod;
} v[1200000];

void push(int nod){
    int st=v[nod].lnod,dr=v[nod].rnod;
    if(v[nod].lazy){
        v[nod].lazy=0;
        v[st].lazy=v[dr].lazy=1;
        v[st].sum=v[st].mar;
        v[dr].sum=v[dr].mar;
    }
}

void update(int nod,int st,int dr,int l,int r){
    if(l<=st && dr<=r){
        v[nod].sum=v[nod].mar;
        v[nod].lazy=1;
        return;
    }
    int mij=(st+dr)/2;
    if(v[nod].lnod==0){
        cnt++;
        v[nod].lnod=cnt;
        v[v[nod].lnod]={0,mij-st+1,0,0,0};
    }
    if(v[nod].rnod==0){
        cnt++;
        v[nod].rnod=cnt;
        v[v[nod].rnod]={0,dr-mij,0,0,0};
    }
    int st1=v[nod].lnod,dr1=v[nod].rnod;
    push(nod);
    if(l<=mij) update(st1,st,mij,l,r);
    if(mij+1<=r) update(dr1,mij+1,dr,l,r);
    v[nod].sum=v[st1].sum+v[dr1].sum;
}

int query(int nod,int st,int dr,int l,int r){
    if(l<=st && dr<=r) return v[nod].sum;
    int mij=(st+dr)/2;
    if(v[nod].lnod==0){
        cnt++;
        v[nod].lnod=cnt;
        v[v[nod].lnod]={0,mij-st+1,0,0,0};
    }
    if(v[nod].rnod==0){
        cnt++;
        v[nod].rnod=cnt;
        v[v[nod].rnod]={0,dr-mij,0,0,0};
    }
    int st1=v[nod].lnod,dr1=v[nod].rnod,rasp=0;
    push(nod);
    if(l<=mij) rasp+=query(st1,st,mij,l,r);
    if(mij+1<=r) rasp+=query(dr1,mij+1,dr,l,r);
    return rasp;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,i,cer,aux=0,a,b,rasp;
    cin>>n;
    cnt=1;
    v[1]={0,n,0,0,0};
    for(i=1;i<=n;i++){
        cin>>cer>>a>>b;
        if(cer==1){
            rasp=query(1,1,1e9,a+aux,b+aux);
            cout<<rasp<<"\n";
            aux=rasp;
        }else{
            update(1,1,1e9,a+aux,b+aux);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100