Submission #636068

#	Time	Username	Problem	Language	Result	Execution time	Memory
636068		tvladm2009	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	455 ms	207660 KiB

apple

// solutia mea e buna dar e prea prost oj.uz ul si iau 0 ca imi paca un test cu tle, asa ca am furat un cod
// credite : stefantaga
#include <bits/stdc++.h>
 
using namespace std;
struct Arbore{
    int st,dr;
    Arbore *fiust,*fiudr;
    int suma,lazy;
    Arbore (int l,int r)
    {
        st=l;
        dr=r;
        suma=lazy=0;
        fiust=fiudr=NULL;
    }
};
void propaga(Arbore *&acum,Arbore *&fiust, Arbore *&fiudr, int st,int dr)
{
    if (st==dr)
    {
        return;
    }
    if (acum->lazy==0)
    {
        return;
    }
    int mij=(st+dr)/2;
    if (fiust==NULL)
    {
        fiust = new Arbore(st,mij);
    }
    if (fiudr==NULL)
    {
        fiudr = new Arbore(mij+1,dr);
    }
    fiust->lazy=1;
    fiust->suma=fiust->dr-fiust->st+1;
    fiudr->lazy=1;
    fiudr->suma=fiudr->dr-fiudr->st+1;
    acum->lazy=0;
}
void update(Arbore *&acum,int st,int dr,int ua,int ub)
{
    if (ub<st||dr<ua)
    {
        return;
    }
    if (acum==NULL)
    {
        acum = new Arbore (st,dr);
    }
    if (ua<=st&&dr<=ub)
    {
        acum->suma=dr-st+1;
        acum->lazy=1;
        return;
    }
    propaga(acum,acum->fiust,acum->fiudr,st,dr);
    int mij=(st+dr)/2;
    update(acum->fiust,st,mij,ua,ub);
    update(acum->fiudr,mij+1,dr,ua,ub);
    int stanga,dreapta;
    if (acum->fiust==NULL)
    {
        stanga=0;
    }
    else
    {
        stanga=acum->fiust->suma;
    }
    if (acum->fiudr==NULL)
    {
        dreapta=0;
    }
    else
    {
        dreapta=acum->fiudr->suma;
    }
    acum->suma=stanga+dreapta;
}
int query(Arbore *&acum, int st,int dr,int ua,int ub)
{
    if (ub<st||dr<ua)
    {
        return 0;
    }
    if (acum==NULL)
    {
        return 0;
    }
    if (ua<=st&&dr<=ub)
    {
        return acum->suma;
    }
    propaga(acum,acum->fiust,acum->fiudr,st,dr);
    int mij=(st+dr)/2;
    return query(acum->fiust,st,mij,ua,ub)+query(acum->fiudr,mij+1,dr,ua,ub);
}
int n,i;
Arbore *arb;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n;
    int lim=1e9;
    arb = new Arbore (1,lim);
    int sol=0;
    for (i=1;i<=n;i++)
    {
        int tip,st,dr;
        cin>>tip>>st>>dr;
        st+=sol;
        dr+=sol;
        if (tip==1)
        {
            sol=query(arb,1,lim,st,dr);
            cout<<sol<<'\n';
        }
        else
        {
            update(arb,1,lim,st,dr);
        }
    }
    return 0;
}

• Subtask 1: 100 / 100