Submission #771559

#	Time	Username	Problem	Language	Result	Execution time	Memory
771559		taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	367 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 int
#define endl '\n'
const ll mod = 1e9+7;

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=nullptr;
    }

    ~node()
    {
        delete leftchild;
        delete rightchild;
    }
};
node *root=new node(1, 1e9);

void extend(node *root)
{
    if (root->leftchild==nullptr && root->l!=root->r)
    {
        ll mid=(root->l+root->r)/2;
        if (root->leftchild==nullptr) root->leftchild=new node(root->l, mid);
        if (root->rightchild==nullptr) root->rightchild=new node(mid+1, root->r);
    }
}

void down(node *root)
{
    if (root->lazy!=0)
    {
        root->sum=(root->r-root->l+1)*root->lazy;
        if (root->l!=root->r)
        {
            extend(root);
            root->leftchild->lazy=root->lazy;
            root->rightchild->lazy=root->lazy;
        }   
        root->lazy=0;
    }
}

void update(node *root, ll u, ll v, ll val)
{
    down(root);
    if (root->l>v || root->r<u || u>v) return;   
    if (u<=root->l && root->r<=v) 
    {
        root->lazy=val;
        down(root);   
        return;
    }
    extend(root);
    update(root->leftchild, u, v, val);
    update(root->rightchild, u, v, val);
    root->sum = root->leftchild->sum + root->rightchild->sum;  
}

ll query(node *root, ll u, ll v)
{
    down(root);
    if (root->l>v || root->r<u || u>v) return 0;
    if (u<=root->l && root->r<=v) return root->sum;
    extend(root);
    return query(root->leftchild, u, v) + query(root->rightchild, u, v);
}
ll q, c;

void solve()
{
    cin>>q;
    while (q--)
    {
        ll type, l, r; cin>>type>>l>>r; l+=c; r+=c; assert(l<=1e9 && r<=1e9);
        if (type==1) c=query(root, l, r), cout<<c<<endl;
        else update(root, l, r, 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

• Subtask 1: 0 / 100