Submission #881736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
881736	2023-12-01T19:56:34 Z	alexdd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	202 ms	136612 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	9 ms	2520 KB	Output is correct
5	Correct	10 ms	2596 KB	Output is correct
6	Correct	12 ms	2636 KB	Output is correct
7	Correct	10 ms	2776 KB	Output is correct
8	Correct	57 ms	17868 KB	Output is correct
9	Correct	116 ms	35416 KB	Output is correct
10	Correct	124 ms	35248 KB	Output is correct
11	Correct	123 ms	34732 KB	Output is correct
12	Correct	125 ms	34484 KB	Output is correct
13	Correct	143 ms	70560 KB	Output is correct
14	Correct	134 ms	70052 KB	Output is correct
15	Correct	202 ms	134588 KB	Output is correct
16	Correct	197 ms	136612 KB	Output is correct
17	Correct	135 ms	69796 KB	Output is correct
18	Correct	130 ms	68772 KB	Output is correct
19	Correct	194 ms	134792 KB	Output is correct
20	Correct	202 ms	135836 KB	Output is correct