Submission #1051355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051355	2024-08-10T05:11:49 Z	mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	250 ms	262144 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() {
        extend();
        if (lazy) {
            sum = lazy * (r - l + 1);
            if (l != r)
                left->lazy = lazy, right->lazy = lazy;
            lazy = 0;
        }
    }
    void update(int i, int j, int x) {
        push();
        if (i <= l && r <= j) {
            lazy = x;
            push();
            return;
        }
        if (l > j || r < i) return;
        assert(l != r);
        left->update(i, j, x);
        right->update(i, j, x);
        sum = left->sum + right->sum;
    }
    int query(int i, int j) {
        push();
        if (i <= l && r <= j) return sum;
        if (j < l || r < i) return 0;
        assert(l != r);
        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;
        if (t == 1) {
            c = root.query(x + c, y + c);
            cout << c << '\n';
        } else {
            root.update(x + c, y + c, 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;
      |                     ~~^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	8756 KB	Output is correct
5	Correct	12 ms	10644 KB	Output is correct
6	Correct	12 ms	10332 KB	Output is correct
7	Correct	12 ms	10584 KB	Output is correct
8	Correct	103 ms	79140 KB	Output is correct
9	Correct	246 ms	131396 KB	Output is correct
10	Correct	221 ms	150868 KB	Output is correct
11	Correct	248 ms	163408 KB	Output is correct
12	Correct	236 ms	169044 KB	Output is correct
13	Correct	217 ms	207696 KB	Output is correct
14	Correct	250 ms	209744 KB	Output is correct
15	Runtime error	241 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-