oj.uz

Submission #691668

# Submission time Handle Problem Language Result Execution time Memory
691668 2023-01-31T11:45:43 Z stevancv Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 171 ms 65444 KB 
#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[20 * N], lc[20 * N], rc[20 * N], lzy[20 * 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;
    ll C = 0;
    while (q--) {
        int t;
        ll xx, yy;
        cin >> t >> xx >> yy;
        int x = xx + C; int y = yy + C;
        if (t == 1) {
            int k = Get(root, 1, M, x, y);
            cout << k << en;
            C = k;
        }
        else Set(root, 1, M, x, y);
    }
    return 0;
}

Compilation message

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 13 ms 3156 KB Output is correct
5 Correct 16 ms 3876 KB Output is correct
6 Correct 19 ms 3760 KB Output is correct
7 Correct 16 ms 3828 KB Output is correct
8 Correct 117 ms 26836 KB Output is correct
9 Runtime error 171 ms 65444 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -