Submission #490096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490096	2021-11-25T14:18:36 Z	stefantaga	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	405 ms	207940 KB

apple

#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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	12 ms	4876 KB	Output is correct
5	Correct	19 ms	5964 KB	Output is correct
6	Correct	16 ms	5836 KB	Output is correct
7	Correct	16 ms	5964 KB	Output is correct
8	Correct	124 ms	44552 KB	Output is correct
9	Correct	253 ms	77228 KB	Output is correct
10	Correct	264 ms	85060 KB	Output is correct
11	Correct	285 ms	91020 KB	Output is correct
12	Correct	275 ms	93972 KB	Output is correct
13	Correct	244 ms	109216 KB	Output is correct
14	Correct	299 ms	110956 KB	Output is correct
15	Correct	397 ms	201772 KB	Output is correct
16	Correct	405 ms	203056 KB	Output is correct
17	Correct	256 ms	114880 KB	Output is correct
18	Correct	303 ms	114820 KB	Output is correct
19	Correct	405 ms	207940 KB	Output is correct
20	Correct	393 ms	207608 KB	Output is correct