Submission #881737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881737	2023-12-01T19:56:55 Z	alexdd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	168 ms	70480 KB

apple

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
struct node
{
    int sum,lazy;
    int tole,tori;
};
vector<node> aint;
void propagate(int nod, int st, int dr)
{
    if(aint[nod].lazy==0)
        return;
    int le = aint[nod].tole;
    int ri = aint[nod].tori;
    int mij=(st+dr)/2;
    aint[le].sum = mij-st+1;
    aint[le].lazy = 1;
    aint[ri].sum = dr-mij;
    aint[ri].lazy = 1;
    aint[nod].lazy=0;
}
void upd(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return;
    if(st==le && dr==ri)
    {
        aint[nod].sum = ri-le+1;
        aint[nod].lazy=1;
        return;
    }
    if(aint[nod].tole==-1)
    {
        aint[nod].tole=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    if(aint[nod].tori==-1)
    {
        aint[nod].tori=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    propagate(nod,st,dr);
    int mij=(st+dr)/2;
    upd(aint[nod].tole,st,mij,le,min(mij,ri));
    upd(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
    aint[nod].sum = aint[aint[nod].tole].sum + aint[aint[nod].tori].sum;
}
int qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return 0;
    if(le==st && dr==ri)
        return aint[nod].sum;
    if(aint[nod].tole==-1)
    {
        aint[nod].tole=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    if(aint[nod].tori==-1)
    {
        aint[nod].tori=aint.size();
        aint.push_back({0,0,-1,-1});
    }
    propagate(nod,st,dr);
    int mij=(st+dr)/2;
    return qry(aint[nod].tole,st,mij,le,min(mij,ri)) +
           qry(aint[nod].tori,mij+1,dr,max(mij+1,le),ri);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    aint.reserve(40000000);
    int m,c=0,d,x,y;
    cin>>m;
    aint.push_back({0,0,-1,-1});
    while(m--)
    {
        cin>>d>>x>>y;
        x+=c;
        y+=c;
        if(d==1)
        {
            c = qry(0,1,INF,x,y);
            cout<<c<<"\n";
        }
        else
        {
            upd(0,1,INF,x,y);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	3676 KB	Output is correct
5	Correct	9 ms	2816 KB	Output is correct
6	Correct	9 ms	4188 KB	Output is correct
7	Correct	10 ms	3676 KB	Output is correct
8	Correct	52 ms	16552 KB	Output is correct
9	Correct	109 ms	27736 KB	Output is correct
10	Correct	112 ms	30244 KB	Output is correct
11	Correct	116 ms	31312 KB	Output is correct
12	Correct	116 ms	31576 KB	Output is correct
13	Correct	122 ms	37460 KB	Output is correct
14	Correct	114 ms	37084 KB	Output is correct
15	Correct	155 ms	67408 KB	Output is correct
16	Correct	159 ms	68180 KB	Output is correct
17	Correct	116 ms	39008 KB	Output is correct
18	Correct	117 ms	39760 KB	Output is correct
19	Correct	168 ms	69460 KB	Output is correct
20	Correct	161 ms	70480 KB	Output is correct