Submission #691676

#	Time	Username	Problem	Language	Result	Execution time	Memory
691676		stevancv	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	421 ms	132800 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e9;
const ll linf = 1e18;
int st[100 * N], lc[100 * N], rc[100 * N], lzy[100 * N], tsz, root;
void Propagate(int c, int l, int r) {
    if (lzy[c] == 0) return;
    if (l < r) {
        if (!lc[c]) lc[c] = ++tsz;
        lzy[lc[c]] = lzy[c];
        if (!rc[c]) rc[c] = ++tsz;
        lzy[rc[c]] = lzy[c];
    }
    st[c] = r - l + 1;
    lzy[c] = 0;
}
void Set(int &c, int l, int r, int ql, int qr) {
    if (!c) c = ++tsz;
    Propagate(c, l, r);
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
        lzy[c] = 1;
        Propagate(c, l, r);
        return;
    }
    int mid = l + r >> 1;
    Set(lc[c], l, mid, ql, qr);
    Set(rc[c], mid + 1, r, ql, qr);
    st[c] = st[lc[c]] + st[rc[c]];
}
int Get(int &c, int l, int r, int ql, int qr) {
    if (!c) c = ++tsz;
    Propagate(c, l, r);
    if (r < ql || qr < l) return 0;
    if (ql <= l && r <= qr) return st[c];
    int mid = l + r >> 1;
    return Get(lc[c], l, mid, ql, qr) + Get(rc[c], mid + 1, r, ql, qr);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q; cin >> q;
    int C = 0;
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        x += C; y += C;
        if (t == 1) {
            C = Get(root, 1, M, x, y);
            cout << C << en;
        }
        else Set(root, 1, M, x, y);
    }
    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'void Set(int&, int, int, int, int)':
apple.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int mid = l + r >> 1;
      |               ~~^~~
apple.cpp: In function 'int Get(int&, int, int, int, int)':
apple.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 100 / 100