#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 <= 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
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:29:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | if (_l < l + r >> 1) ch[0]->modify(_l, _r, _d);
| ~~^~~
game.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | if (l + r >> 1 < _r) ch[1]->modify(_l, _r, _d);
| ~~^~~
game.cpp: In member function 'int seg::query(int)':
game.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | return ch[i >= l + r >> 1]->query(i);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
94148 KB |
Output is correct |
| 2 |
Incorrect |
99 ms |
94224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
94148 KB |
Output is correct |
| 2 |
Incorrect |
99 ms |
94224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
94148 KB |
Output is correct |
| 2 |
Incorrect |
99 ms |
94224 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
