Submission #771447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771447	2023-07-03T03:04:34 Z	taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	340 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 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;
                if (l!=r)
                {
                    extend();
                    leftchild->lazy=lazy;
                    rightchild->lazy=lazy;
                }   
                lazy=0;
            }
        }
    };
    node *root;

    sparse_segment_tree(ll _l, ll _r)
    {
        root=new node(_l, _r);
    } 

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

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

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(seg.root, l+c, r+c), cout<<c<<endl;
        else seg.update(seg.root, 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	14 ms	11420 KB	Output is correct
5	Correct	19 ms	13820 KB	Output is correct
6	Correct	17 ms	13388 KB	Output is correct
7	Correct	18 ms	13908 KB	Output is correct
8	Correct	151 ms	103372 KB	Output is correct
9	Correct	303 ms	175896 KB	Output is correct
10	Correct	319 ms	197368 KB	Output is correct
11	Correct	340 ms	213944 KB	Output is correct
12	Correct	335 ms	221376 KB	Output is correct
13	Runtime error	306 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-