Submission #840312

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
840312	2023-08-31T09:47:00 Z	taitruong270	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	333 ms	262144 KB

apple

/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
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
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
 
struct sparse_segment_tree  //luu y bo nho n.logn nen de toan cuc 
{
    struct node 
    {
        ll sum, lazy;
        node *leftchild, *rightchild;
    
        node()
        {
            sum=0;
            lazy=0;
            leftchild=rightchild=NULL;
        }
    
        ~node()
        {
            delete leftchild;
            delete rightchild;
        }
    };
    ll maxn;
    node *root=new node();
 
    sparse_segment_tree(){}
    sparse_segment_tree(ll _maxn)
    {
        maxn=_maxn;
    }
    
    void extend(node *root, ll l, ll r)
    {
        if (l!=r)
        {
            if (root->leftchild==NULL) root->leftchild=new node();
            if (root->rightchild==NULL) root->rightchild=new node();
        }
    }
    
    void down(node *root, ll l, ll r)
    {
        if (root->lazy!=0)
        {
            root->sum=(r-l+1)*root->lazy;
            if (l!=r)
            {
                extend(root, l, r);
                root->leftchild->lazy=root->lazy;
                root->rightchild->lazy=root->lazy;
            }   
            root->lazy=0;
        }
    }
    
    void update(node *root, ll l, ll r, ll &u, ll &v, ll &val)
    {
        down(root, l, r);
        if (l>v || r<u || u>v) return;   
        if (u<=l && r<=v) 
        {
            root->lazy=val;
            down(root, l, r);   
            return;
        }
        extend(root, l, r);
        ll mid=(l+r)/2;
        update(root->leftchild, l, mid, u, v, val);
        update(root->rightchild, mid+1, r, u, v, val);
        root->sum = root->leftchild->sum + root->rightchild->sum;  
    }
    
    ll query(node *root, ll l, ll r, ll &u, ll &v)
    {
        down(root, l, r);
        if (l>v || r<u || u>v) return 0;
        if (u<=l && r<=v) return root->sum;
        extend(root, l, r);
        ll mid=(l+r)/2;
        return query(root->leftchild, l, mid, u, v) + query(root->rightchild, mid+1, r, u, v);
    }
 
    void update(ll u, ll v, ll val)
    {
        update(root, 1, maxn, u, v, val);
    }
 
    ll query(ll u, ll v)
    {
        return query(root, 1, maxn, u, v);
    }
};
sparse_segment_tree seg(1e9);
 
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=seg.query(l, r), cout<<c<<endl;
        else seg.update(l, r, 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	14 ms	8516 KB	Output is correct
5	Correct	16 ms	10356 KB	Output is correct
6	Correct	15 ms	9940 KB	Output is correct
7	Correct	19 ms	10324 KB	Output is correct
8	Correct	139 ms	76996 KB	Output is correct
9	Correct	293 ms	130784 KB	Output is correct
10	Correct	294 ms	146896 KB	Output is correct
11	Correct	301 ms	159300 KB	Output is correct
12	Correct	297 ms	164804 KB	Output is correct
13	Correct	294 ms	205028 KB	Output is correct
14	Correct	284 ms	206960 KB	Output is correct
15	Runtime error	333 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-