Submission #1088264

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

apple

#include <bits/stdc++.h>

using namespace std;

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

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

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);
    		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")
      |

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	13 ms	8536 KB	Output is correct
5	Correct	15 ms	10328 KB	Output is correct
6	Correct	26 ms	10072 KB	Output is correct
7	Correct	16 ms	10332 KB	Output is correct
8	Correct	142 ms	76940 KB	Output is correct
9	Correct	272 ms	131188 KB	Output is correct
10	Correct	279 ms	146768 KB	Output is correct
11	Correct	308 ms	159460 KB	Output is correct
12	Correct	267 ms	164948 KB	Output is correct
13	Correct	249 ms	205180 KB	Output is correct
14	Correct	262 ms	207188 KB	Output is correct
15	Runtime error	282 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-