Submission #771454

#	Time	Username	Problem	Language	Result	Execution time	Memory
771454		taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	389 ms	262144 KiB

apple

/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
I hated every minute of training, but I said, ‘Don’t quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
                                          Noi dau + Suy ngam = Tien bo 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll mod = 1e9+7;
 
struct sparse_segment_tree
{
    struct node 
    {
        ll l, r, sum, lazy;
        node *leftchild, *rightchild;
 
        node(ll _l, ll _r)
        {
            l=_l;
            r=_r;
            sum=0;
            lazy=0;
            leftchild=rightchild=NULL;
        }
 
        ~node()
        {
            delete leftchild;
            delete rightchild;
        }
 
        void extend()
        {
            if (l!=r)
            {
                ll mid=(l+r)/2;
                if (leftchild==NULL) leftchild=new node(l, mid);
                if (rightchild==NULL) rightchild=new node(mid+1, r);
            }
        }
 
        void down()
        {
            if (lazy!=0)
            {
                sum=(r-l+1)*lazy;
                if (l!=r)
                {
                    extend();
                    leftchild->lazy=lazy;
                    rightchild->lazy=lazy;
                }   
                lazy=0;
            }
        }
 
        void update(ll u, ll v, ll val)
        {
            down();
            if (l>v || r<u) return;   
            if (u<=l && r<=v) 
            {
                lazy=val;
                down();   
                return;
            }
            extend();
            leftchild->update(u, v, val);
            rightchild->update(u, v, val);
            sum = leftchild->sum + rightchild->sum;  
        }
 
        ll query(ll u, ll v)
        {
            down();
            if (l>v || r<u) return 0;
            if (u<=l && r<=v) return sum;
            extend();
            return leftchild->query(u, v)+rightchild->query(u, v);
        }
    };
    node *root;
 
    sparse_segment_tree(ll _l, ll _r)
    {
        root=new node(_l, _r);
    } 
 
    void update(ll l, ll r, ll val)
    {
        root->update(l, r, val);
    }
 
    ll query(ll l, ll r)
    {
        return root->query(l, r);
    }
};
 
sparse_segment_tree seg(1, 1e9);
ll q, c;
 
void solve()
{
    cin>>q;
    while (q--)
    {
        ll type, l, r; cin>>type>>l>>r;
        if (type==1) c=seg.query(l+c, r+c), cout<<c<<endl;
        else seg.update(l+c, r+c, 1);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

• Subtask 1: 0 / 100