Submission #1051349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051349	2024-08-10T05:05:03 Z	mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	258 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, (1 << 30) - 1);
    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	604 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	8892 KB	Output is correct
5	Correct	12 ms	10844 KB	Output is correct
6	Correct	13 ms	10332 KB	Output is correct
7	Correct	12 ms	10752 KB	Output is correct
8	Correct	106 ms	79952 KB	Output is correct
9	Correct	207 ms	133180 KB	Output is correct
10	Correct	233 ms	152544 KB	Output is correct
11	Correct	235 ms	165172 KB	Output is correct
12	Correct	232 ms	170836 KB	Output is correct
13	Correct	220 ms	209672 KB	Output is correct
14	Correct	233 ms	211828 KB	Output is correct
15	Runtime error	258 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-