Submission #636068

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636068	2022-08-27T21:59:32 Z	tvladm2009	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	455 ms	207660 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	12 ms	4956 KB	Output is correct
5	Correct	16 ms	5972 KB	Output is correct
6	Correct	15 ms	5844 KB	Output is correct
7	Correct	15 ms	5928 KB	Output is correct
8	Correct	128 ms	44564 KB	Output is correct
9	Correct	249 ms	77256 KB	Output is correct
10	Correct	258 ms	85328 KB	Output is correct
11	Correct	267 ms	91620 KB	Output is correct
12	Correct	271 ms	94520 KB	Output is correct
13	Correct	260 ms	110016 KB	Output is correct
14	Correct	238 ms	110988 KB	Output is correct
15	Correct	414 ms	201680 KB	Output is correct
16	Correct	455 ms	203216 KB	Output is correct
17	Correct	248 ms	114892 KB	Output is correct
18	Correct	255 ms	114836 KB	Output is correct
19	Correct	388 ms	207656 KB	Output is correct
20	Correct	396 ms	207660 KB	Output is correct