Submission #1051354

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051354	2024-08-10T05:08:20 Z	mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	254 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;
        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;
        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	10 ms	8840 KB	Output is correct
5	Correct	13 ms	10552 KB	Output is correct
6	Correct	15 ms	10364 KB	Output is correct
7	Correct	13 ms	10604 KB	Output is correct
8	Correct	111 ms	79184 KB	Output is correct
9	Correct	217 ms	131312 KB	Output is correct
10	Correct	246 ms	150864 KB	Output is correct
11	Correct	240 ms	163528 KB	Output is correct
12	Correct	238 ms	169104 KB	Output is correct
13	Correct	237 ms	207576 KB	Output is correct
14	Correct	225 ms	209580 KB	Output is correct
15	Runtime error	254 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-