Submission #1267573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267573		tudorh	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	433 ms	199848 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
struct nod
{
    nod*st=nullptr,*dr=nullptr;
    int sum=0,lazy=0;
}*aint;
int ans=0,aux;
void push(nod*v,int st,int dr)
{
    if(st==dr || !v->lazy)
        return;
    if(!v->st)
        v->st=new nod;
    if(!v->dr)
        v->dr=new nod;
    int mid=(st+dr)/2;
    v->st->sum=v->st->lazy=mid-st+1;
    v->dr->sum=v->dr->lazy=dr-mid;
    v->lazy=0;
}
void query(nod*v,int st,int dr,int qst,int qdr)
{
    push(v,st,dr);
    if(st>=qst && dr<=qdr)
        ans+=v->sum;
    else
    {
        int mid=(st+dr)/2;
        if(qst<=mid && v->st)
            query(v->st,st,mid,qst,qdr);
        if(qdr>mid && v->dr)
            query(v->dr,mid+1,dr,qst,qdr);
    }
}
void update(nod*v,int st,int dr,int qst,int qdr)
{
    push(v,st,dr);
    if(st>=qst && dr<=qdr)
        v->lazy=v->sum=dr-st+1;
    else
    {
        int mid=(st+dr)/2;
        if(qst<=mid)
        {
            if(!v->st)
                v->st=new nod;
            update(v->st,st,mid,qst,qdr);
        }
        if(qdr>mid)
        {
            if(!v->dr)
                v->dr=new nod;
            update(v->dr,mid+1,dr,qst,qdr);
        }
        v->sum=0;
        if(v->st)
            v->sum+=v->st->sum;
        if(v->dr)
            v->sum+=v->dr->sum;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int n,t,st,dr;
    cin>>n;
    aint=new nod;
    while(n--)
    {
        cin>>t>>st>>dr;
        if(t==2)
            update(aint,1,1e9,st+ans,dr+ans);
        else
        {
            aux=ans;
            ans=0;
            query(aint,1,1e9,st+aux,dr+aux);
            cout<<ans<<'\n';
        }
    }
    return 0;
}

• Subtask 1: 100 / 100