Submission #881738

#	Time	Username	Problem	Language	Result	Execution time	Memory
881738		alexdd	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	173 ms	134332 KiB

apple

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
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);
    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 / 100