Submission #1051385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051385	2024-08-10T05:45:17 Z	mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	240 ms	209532 KB

apple

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LSOne(S) ((S) & -(S))

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int N = 1e9 + 10;
struct node {
    int sum = 0, lazy = 0, l, r;
    node *left, *right;
    node(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {}

    void extend() {
        if (!left && l != r) {
            int m = l + r >> 1;
            left = new node(l, m);
            right = new node(m + 1, r);
        }
    }

    void push() {  // lazy only for children; used when children are created when necessary
        if (!lazy || l == r || !left) return;
        left->lazy = lazy, right->lazy = lazy;
        int m = l + r >> 1;
        left->sum = (m - l + 1) * lazy, right->sum = (r - m) * lazy;
        lazy = 0;
    }

    void update(int i, int j, int x) {
        if (i <= l && r <= j) {
            lazy = x;
            sum = (r - l + 1) * x;
            return;
        }
        if (l > j || r < i) return;
        extend(), push();
        left->update(i, j, x);
        right->update(i, j, x);
        sum = left->sum + right->sum;
    }
    int query(int i, int j) {
        if (i <= l && r <= j) return sum;
        if (j < l || r < i) return 0;
        extend(), push();
        return left->query(i, j) + right->query(i, j);
    }
};

void solve() {
    int q;
    cin >> q;

    node root(0, INT_MAX);
    int c = 0;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        x += c, y += c;
        if (t == 1) {
            c = root.query(x, y);
            cout << c << '\n';
        } else {
            root.update(x, y, 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        solve();
    }
    return 0;
}

Compilation message

apple.cpp: In member function 'void node::extend()':
apple.cpp:38:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |             int m = l + r >> 1;
      |                     ~~^~~
apple.cpp: In member function 'void node::push()':
apple.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	4956 KB	Output is correct
5	Correct	9 ms	6060 KB	Output is correct
6	Correct	8 ms	5724 KB	Output is correct
7	Correct	8 ms	6084 KB	Output is correct
8	Correct	70 ms	44408 KB	Output is correct
9	Correct	152 ms	75344 KB	Output is correct
10	Correct	157 ms	84816 KB	Output is correct
11	Correct	149 ms	91220 KB	Output is correct
12	Correct	160 ms	94040 KB	Output is correct
13	Correct	138 ms	108880 KB	Output is correct
14	Correct	135 ms	109892 KB	Output is correct
15	Correct	240 ms	203488 KB	Output is correct
16	Correct	236 ms	205000 KB	Output is correct
17	Correct	144 ms	115800 KB	Output is correct
18	Correct	150 ms	115792 KB	Output is correct
19	Correct	236 ms	209492 KB	Output is correct
20	Correct	230 ms	209532 KB	Output is correct