Submission #788071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788071	2023-07-19T17:48:11 Z	lamduybao03	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	325 ms	209484 KB

apple

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node {
    int sum;
    int lazy;
    node* left;
    node* right;
    node() {
        sum = 0;
        lazy = 0;
        left = nullptr;
        right = nullptr;
    }
    node* new_node(node* p) {
        if(p != nullptr)
            return p;
        else
            return new node;
    }
    void down(int len) {
        if(lazy != -1) {
            left = new_node(left);
            right = new_node(right);
            left->sum = (len - len / 2) * lazy;
            right->sum = (len / 2) * lazy;
            left->lazy = right->lazy = lazy;
            lazy = -1;
        }
    }
    void update(int u, int v, int l, int r) {
        if(u <= l && r <= v) {
            sum = r-l+1;
            lazy = 1;
        }
        else if(u <= r && l <= v) {
            down(r-l+1);
            int m = l + r >> 1;
            left->update(u, v, l, m);
            right->update(u, v, m+1, r);
            sum = left->sum + right->sum;
        }
    }
    int query(int u, int v, int l, int r) {
        if(u <= l && r <= v)
            return sum;
        else if(u <= r && l <= v) {
            down(r-l+1);
            int m = l + r >> 1;
            int s1 = left->query(u, v, l, m);
            int s2 = right->query(u, v, m+1, r);
            return s1 + s2;
        }
        return 0;
    }
    void update(int u, int v) {
        update(u, v, INT_MIN, INT_MAX);
    }
    int query(int u, int v) {
        return query(u, v, INT_MIN, INT_MAX);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifndef ONLINE_JUDGE
//        freopen("input.txt", "r", stdin);
    #endif
    int q; cin >> q;
    int c = 0;
    node root;
    while(q--) {
        int id; cin >> id;
        if(id == 2) {
            int l, r;
            cin >> l >> r;
            root.update(l + c, r + c);
        }
        else {
            int l, r;
            cin >> l >> r;
            int ans = root.query(l + c, r + c);
            c = ans;
            cout << ans << "\n";
        }
    }
}

Compilation message

apple.cpp: In member function 'void node::update(long long int, long long int, long long int, long long int)':
apple.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |             int m = l + r >> 1;
      |                     ~~^~~
apple.cpp: In member function 'long long int node::query(long long int, long long int, long long int, long long int)':
apple.cpp:50:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	9 ms	5076 KB	Output is correct
5	Correct	11 ms	6028 KB	Output is correct
6	Correct	14 ms	5832 KB	Output is correct
7	Correct	11 ms	6100 KB	Output is correct
8	Correct	93 ms	45204 KB	Output is correct
9	Correct	194 ms	76880 KB	Output is correct
10	Correct	209 ms	86584 KB	Output is correct
11	Correct	202 ms	93064 KB	Output is correct
12	Correct	204 ms	95820 KB	Output is correct
13	Correct	180 ms	110980 KB	Output is correct
14	Correct	182 ms	112016 KB	Output is correct
15	Correct	325 ms	203468 KB	Output is correct
16	Correct	308 ms	205012 KB	Output is correct
17	Correct	190 ms	115584 KB	Output is correct
18	Correct	188 ms	115784 KB	Output is correct
19	Correct	308 ms	209484 KB	Output is correct
20	Correct	317 ms	209384 KB	Output is correct