Submission #771455

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771455	2023-07-03T03:28:57 Z	taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	413 ms	262144 KB

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

    void extend()
    {
        if (l!=r)
        {
            ll mid=(l+r)/2;
            if (leftchild==nullptr) leftchild=new node(l, mid);
            if (rightchild==nullptr) 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 || u>v) 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 || u>v) return 0;
        if (u<=l && r<=v) return sum;
        extend();
        return leftchild->query(u, v)+rightchild->query(u, v);
    }
};
node root(1, 1e9+10);
ll q, c;

void solve()
{
    cin>>q;
    while (q--)
    {
        ll type, l, r; cin>>type>>l>>r; l+=c; r+=c;
        if (type==1) c=root.query(l, r), cout<<c<<endl;
        else root.update(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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	15 ms	8532 KB	Output is correct
5	Correct	20 ms	10392 KB	Output is correct
6	Correct	21 ms	9948 KB	Output is correct
7	Correct	20 ms	10324 KB	Output is correct
8	Correct	193 ms	77008 KB	Output is correct
9	Correct	363 ms	130720 KB	Output is correct
10	Correct	375 ms	146936 KB	Output is correct
11	Correct	403 ms	159292 KB	Output is correct
12	Correct	413 ms	164808 KB	Output is correct
13	Correct	391 ms	207156 KB	Output is correct
14	Correct	374 ms	209080 KB	Output is correct
15	Runtime error	340 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-