Submission #1051385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051385		mnasser02	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	240 ms	209532 KiB

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 (stderr)

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 / 100