Submission #1088272

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1088272	2024-09-14T07:36:56 Z	rayan_bd	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	326 ms	262144 KB

apple

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization("Ofast")

#define ll long long

const int mxN = 1e9+1000;

struct SegTree {
    struct Node {
        ll val = 0, lazy = 0;
        Node* left = NULL;
        Node* right = NULL;
    };
    
    typedef Node* root;
    root R = NULL;

    SegTree(int n) {
        R = new Node();
    }

    void push(root nd, ll l, ll r) {
        if (!nd || nd->lazy == 0) return;
        nd->val = (r - l + 1) * nd->lazy;
        if (r - l > 0) {
            if (nd->left == NULL) nd->left = new Node;
            if (nd->right == NULL) nd->right = new Node;
            nd->left->lazy = nd->lazy;
            nd->right->lazy = nd->lazy;
        }
        nd->lazy = 0; 
    }

    void update(root nd, ll start, ll end, ll l, ll r) {
        if (!nd) return;
        push(nd, start, end);
        if (start > r || end < l) return;
        if (start >= l && end <= r) {
            nd->lazy = 1; 
            push(nd, start, end); 
            return;
        }
        ll mid = start + (end - start) / 2;
        if (nd->left == NULL) nd->left = new Node;
        if (nd->right == NULL) nd->right = new Node;
        update(nd->left, start, mid, l, r);
        update(nd->right, mid + 1, end, l, r);
        nd->val = (nd->left ? nd->left->val : 0) + (nd->right ? nd->right->val : 0);
    }

    ll qry(root nd, ll start, ll end, ll l, ll r) {
        if (!nd) return 0;
        push(nd, start, end);
        if (start > r || end < l) return 0;
        if (start >= l && end <= r) return nd->val;
        ll mid = start + (end - start) / 2;
        return qry(nd->left, start, mid, l, r) + qry(nd->right, mid + 1, end, l, r);
    }

    void del(root nd,ll start,ll end,ll l,ll r){
    	if(!nd) return;
    	push(nd,start,end);
    	if (start > r || end < l) return;
    	if (start >= l && end <= r){
    		delete nd;
    		return;
    	}
    	ll mid = start + (end - start) / 2;
    	del(nd->left,start,mid,l,r);
    	del(nd->right,mid+1,end,l,r);
    	nd->val = (nd->left ? nd->left->val : 0) + (nd->right ? nd->right->val : 0);
    }

    void update(ll l, ll r) {
        update(this->R, 1, mxN, l, r);
    }

    ll qry(ll l, ll r) {
        return qry(this->R, 1, mxN, l, r);
    }

    void del(ll l,ll r){
    	del(this->R,1,mxN,l,r);
    }
};

signed main() {
    


    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    

    ll n,prev=0,e,l,r;cin>>n;
    SegTree seg_tree(mxN);

    while(n--){
    	cin>>e>>l>>r;
    	l+=prev;
    	r+=prev;
    	if(e==1){
    		prev=seg_tree.qry(l,r);
    		//seg_tree.del(1,prev);
    		cout<<prev<<'\n';
    	}else if(e==2){
    		seg_tree.update(l,r);
    	}
    }

    return 0;
}

Compilation message

apple.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
apple.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
apple.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization("Ofast")
      |

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	8792 KB	Output is correct
5	Correct	17 ms	10588 KB	Output is correct
6	Correct	16 ms	10076 KB	Output is correct
7	Correct	15 ms	10588 KB	Output is correct
8	Correct	127 ms	77908 KB	Output is correct
9	Correct	256 ms	132760 KB	Output is correct
10	Correct	280 ms	148560 KB	Output is correct
11	Correct	298 ms	161276 KB	Output is correct
12	Correct	303 ms	166740 KB	Output is correct
13	Correct	284 ms	207312 KB	Output is correct
14	Correct	283 ms	209272 KB	Output is correct
15	Runtime error	326 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-