Submission #577938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577938	2022-06-15T13:41:24 Z	KindaNameless	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	435 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 << 31) - 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;
      |             ^~~
apple.cpp: In function 'int main()':
apple.cpp:80:25: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   80 |     int LIM = (1 << 31) - 1;
      |               ~~~~~~~~~~^~~

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	1 ms	212 KB	Output is correct
4	Correct	20 ms	8344 KB	Output is correct
5	Correct	23 ms	9940 KB	Output is correct
6	Correct	22 ms	9556 KB	Output is correct
7	Correct	25 ms	10028 KB	Output is correct
8	Correct	174 ms	74060 KB	Output is correct
9	Correct	403 ms	130996 KB	Output is correct
10	Correct	388 ms	141260 KB	Output is correct
11	Correct	411 ms	153664 KB	Output is correct
12	Correct	367 ms	158752 KB	Output is correct
13	Correct	374 ms	200684 KB	Output is correct
14	Correct	387 ms	202700 KB	Output is correct
15	Runtime error	435 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-