Submission #1051364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051364	2024-08-10T05:20:57 Z	mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	264 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;
        push();
        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;
        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;
        assert(x && y);
        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;
      |                     ~~^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	8796 KB	Output is correct
5	Correct	12 ms	10680 KB	Output is correct
6	Correct	12 ms	10332 KB	Output is correct
7	Correct	12 ms	10684 KB	Output is correct
8	Correct	103 ms	79100 KB	Output is correct
9	Correct	223 ms	131412 KB	Output is correct
10	Correct	239 ms	150864 KB	Output is correct
11	Correct	264 ms	163408 KB	Output is correct
12	Correct	227 ms	169044 KB	Output is correct
13	Correct	223 ms	207700 KB	Output is correct
14	Correct	224 ms	209556 KB	Output is correct
15	Runtime error	250 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-