Submission #577923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577923	2022-06-15T13:05:37 Z	KindaNameless	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	407 ms	262144 KB

apple

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>
using namespace std;

#define ll long long
#define ld long double

struct Node{
    int sum = 0, lazy = -1, L, R;
    Node *left_child = nullptr, *right_child = nullptr;

    Node(int _l, int _r){
        L = _l; R = _r;
    }

    void extend(){
        if(!left_child && L != R){
            int mid = L + R >> 1;
            left_child = new Node(L, mid);
            right_child = new Node(mid+1, R);
        }
    }

    void push(){
        extend();
        sum = (lazy == -1 ? sum : (R - L + 1));
        if(L != R){
            left_child->lazy = (lazy == -1 ? left_child->lazy : lazy);
            right_child->lazy = (lazy == -1 ? right_child->lazy : lazy);
        }
        lazy = -1;
    }

    void upd(int l, int r){
        push();
        if(r < L || R < l){
            return;
        }
        if(l <= L && R <= r){
            lazy = 1;
            push();
            //cout << "seg : " << L << " " << R << ", sum : " << sum << "\n";
            return;
        }
        int mid = L + R >> 1;
        left_child->upd(l, r);
        right_child->upd(l, r);
        sum = left_child->sum + right_child->sum;
    }

    int query(int l, int r){
        push();
        if(r < L || R < l){
            return 0;
        }
        if(l <= L && R <= r){
            //cout << "seg : " << L << " " << R << ", sum : " << sum << "\n";
            return sum;
        }
        int mid = L + R >> 1;
        return left_child->query(l, r) + right_child->query(l, r);
    }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int LIM = (1 << 30) - 1;

    Node *ST = new Node(0, LIM);

    int M; cin >> M;

    int c = 0;
    while(M--){
        int d, x, y; cin >> d >> x >> y; x--; y--;
        if(d == 1){
            c = ST->query(x + c, y + c);
            cout << c << "\n";
        }
        else{
            ST->upd(x + c, y + c);
        }
    }

    return 0;
}

Compilation message

apple.cpp: In member function 'void Node::extend()':
apple.cpp:30:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |             int mid = L + R >> 1;
      |                       ~~^~~
apple.cpp: In member function 'void Node::upd(int, int)':
apple.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = L + R >> 1;
      |                   ~~^~~
apple.cpp:57:13: warning: unused variable 'mid' [-Wunused-variable]
   57 |         int mid = L + R >> 1;
      |             ^~~
apple.cpp: In member function 'int Node::query(int, int)':
apple.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = L + R >> 1;
      |                   ~~^~~
apple.cpp:72:13: warning: unused variable 'mid' [-Wunused-variable]
   72 |         int mid = L + R >> 1;
      |             ^~~

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	320 KB	Output is correct
4	Correct	21 ms	8392 KB	Output is correct
5	Correct	34 ms	10064 KB	Output is correct
6	Correct	25 ms	9760 KB	Output is correct
7	Correct	29 ms	10140 KB	Output is correct
8	Correct	224 ms	74888 KB	Output is correct
9	Correct	355 ms	132820 KB	Output is correct
10	Correct	377 ms	143088 KB	Output is correct
11	Correct	385 ms	155468 KB	Output is correct
12	Correct	374 ms	160608 KB	Output is correct
13	Correct	384 ms	202780 KB	Output is correct
14	Correct	369 ms	204688 KB	Output is correct
15	Runtime error	407 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-