Submission #399956

#	Time	Username	Problem	Language	Result	Execution time	Memory
399956		syl123456	Simple game (IZhO17_game)	C++17	0 / 100	98 ms	94204 KiB

game

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
struct seg {
    int l, r, v, lz;
    seg *ch[2]{};
    seg(int _l, int _r) : l(_l), r(_r), v(0), lz(0) {
        if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
    }
    void modify(int _l, int _r, int _d) {
        if (_l >= _r) return;
        if (_l <= l && r <= _r) {
            v += _d, lz += _d;
            return;
        }
        push();
        if (_l < l + r >> 1) ch[0]->modify(_l, _r, _d);
        if (l + r >> 1 < _r) ch[1]->modify(_l, _r, _d);
        pull();
    }
    void pull() {
        v = ch[0]->v + ch[1]->v;
    }
    void push() {
        ch[0]->v += lz, ch[1]->v += lz, ch[0]->lz += lz, ch[1]->lz += lz, lz = 0;
    }
    int query(int i) {
        if (l == r - 1) return v;
        push();
        return ch[i >= l + r >> 1]->query(i);
    }
} rt(0, 1e6 + 5);
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n];
    for (int &i : a) cin >> i;
    for (int i = 1; i < n; ++i)
        rt.modify(min(a[i - 1], a[i]) + 1, max(a[i - 1], a[i]), 1);
    while (m--) {
        int ty, x;
        cin >> ty >> x;
        if (ty == 1) {
            int y;
            cin >> y;
            --x;
            if (x) rt.modify(min(a[x - 1], a[x]) + 1, max(a[x - 1], a[x]), -1), rt.modify(min(a[x - 1], y) + 1, max(a[x - 1], y), -1);
            if (x < n - 1) rt.modify(min(a[x + 1], a[x]) + 1, max(a[x + 1], a[x]), -1), rt.modify(min(a[x + 1], y) + 1, max(a[x + 1], y), -1);
            a[x] = y;
        }
        else cout << rt.query(x) << '\n';
    }
}

Compilation message (stderr)

game.cpp: In constructor 'seg::seg(int, int)':
game.cpp:21:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                           ~~^~~
game.cpp:21:74: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         if (l < r - 1) ch[0] = new seg(l, l + r >> 1), ch[1] = new seg(l + r >> 1, r);
      |                                                                        ~~^~~
game.cpp: In member function 'void seg::modify(int, int, int)':
game.cpp:30:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         if (_l < l + r >> 1) ch[0]->modify(_l, _r, _d);
      |                  ~~^~~
game.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         if (l + r >> 1 < _r) ch[1]->modify(_l, _r, _d);
      |             ~~^~~
game.cpp: In member function 'int seg::query(int)':
game.cpp:43:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         return ch[i >= l + r >> 1]->query(i);
      |                        ~~^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51