Submission #1310425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310425		HoriaHaivas	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	264 ms	230484 KiB

apple

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

struct Node
{
    int lson;
    int rson;
    int lazy;
    int apples;
};

Node emptyNode={0,0,0,0};

class AINT
{
public:
    Node aint[12000005];
    int sz;
    void init()
    {
        sz=1;
        aint[1]=emptyNode;
    }

    void prop(int val, int l, int r)
    {
        if (aint[val].lazy==0)
            return;
        aint[val].apples=r-l+1;
        if (l!=r)
        {
            if (aint[val].lson!=0)
                aint[aint[val].lson].lazy=1;
            else
            {
                sz++;
                aint[val].lson=sz;
                aint[sz]=emptyNode;
                aint[sz].lazy=1;
            }
            if (aint[val].rson!=0)
                aint[aint[val].rson].lazy=1;
            else
            {
                sz++;
                aint[val].rson=sz;
                aint[sz]=emptyNode;
                aint[sz].lazy=1;
            }
        }
        aint[val].lazy=0;
    }

    void lazy_update(int l, int r, int val, int qa, int qb)
    {
         prop(val,l,r);
         if (qa<=l && r<=qb)
         {
             aint[val].lazy=1;
             return;
         }
         int mid;
         mid=(l+r)/2;
         if (qa<=mid)
         {
             if (aint[val].lson==0)
             {
                 sz++;
                 aint[val].lson=sz;
                 aint[sz]=emptyNode;
             }
             lazy_update(l,mid,aint[val].lson,qa,qb);
         }
         if (qb>mid)
         {
             if (aint[val].rson==0)
             {
                 sz++;
                 aint[val].rson=sz;
                 aint[sz]=emptyNode;
             }
             lazy_update(mid+1,r,aint[val].rson,qa,qb);
         }
         prop(aint[val].lson,l,mid);
         prop(aint[val].rson,mid+1,r);
         aint[val].apples=aint[aint[val].lson].apples+aint[aint[val].rson].apples;
    }

   int query(int l, int r, int val, int qa, int qb)
   {
       prop(val,l,r);
       if (qa<=l && r<=qb)
       {
           return aint[val].apples;
       }
       int mid,ans;
       mid=(l+r)/2;
       ans=0;
       if (qa<=mid)
       {
           if (aint[val].lson!=0)
               ans+=query(l,mid,aint[val].lson,qa,qb);
       }
       if (qb>mid)
       {
           if (aint[val].rson!=0)
               ans+=query(mid+1,r,aint[val].rson,qa,qb);
       }
       return ans;
   }
} ceva;

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m,i,j,type,x,y,c,res;
    cin >> m;
    ceva.init();
    c=0;
    for (i=1;i<=m;i++)
    {
         cin >> type >> x >> y;
         x+=c;
         y+=c;
         if (type==1)
         {
              res=ceva.query(1,1e9,1,x,y);
              cout << res << "\n";
              c=res;
         }
         else
         {
              ceva.lazy_update(1,1e9,1,x,y);
         }
    }
    return 0;
}

• Subtask 1: 100 / 100