#include <bits/stdc++.h>
#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long ll;
const ll inf = (ll)1e9 + 7;
const ll N = (ll)1e6 + 10;
ll n,m;
ll a[N],type,pos,val;
pair<ll,ll> t[N * 6];
void push (ll v) {
t[v * 2].sc += t[v].sc;
t[v * 2 + 1].sc += t[v].sc;
t[v].fr += t[v].sc;
t[v].sc = 0;
}
void update (ll l,ll r,ll add,ll v = 1,ll tl = 1,ll tr = (N - 6)) {
if (tl > tr)
return;
if (l > tr || tl > r)
return;
if (l <= tl && tr <= r) {
t[v].sc += add;
}
else {
ll tm = (tl + tr) >> 1;
update (l,min(tm,r),add,v * 2,tl,tm);
update (max(tm + 1,l),r,add,v * 2 + 1,tm + 1,tr);
}
}
ll get (ll l,ll v = 1,ll tl = 1,ll tr = (N - 6)) {
push(v);
if (tl > tr)
return 0;
if (tl == tr)
return t[v].fr;
else {
ll tm = (tl + tr) >> 1;
if (l <= tm)
return get(l,v * 2,tl,tm);
else
return get(l,v * 2 + 1,tm + 1,tr);
}
}
int main () {
cin >> n >> m;
for (ll i = 1; i <= n; i ++)
scanf ("%lld", &a[i]);
for (ll i = 2; i <= n; i ++) {
if (a[i - 1] + 1 <= a[i] - 1) {
update (a[i - 1] + 1,a[i] - 1,1);
}
else if(a[i - 1] - 1 >= a[i] + 1)
update (a[i] + 1,a[i - 1] - 1,1);
}
for (ll i = 1; i <= n; i ++)
update (a[i],a[i],1);
while (m --) {
scanf ("%lld", &type);
if (type == 1) {
scanf ("%lld%lld", &pos,&val);
if (pos - 1 > 0) {
if (a[pos - 1] + 1 <= a[pos] - 1)
update (a[pos - 1] + 1,a[pos] - 1,-1);
else if(a[pos - 1] - 1 >= a[pos] + 1)
update (a[pos] + 1,a[pos - 1] - 1,-1);
if (a[pos - 1] + 1 <= val - 1)
update (a[pos - 1] + 1,val - 1,1);
else if(a[pos - 1] - 1 >= val + 1)
update (val + 1,a[pos - 1] - 1,1);
}
if (pos + 1 <= n) {
if (a[pos + 1] + 1 <= a[pos] - 1)
update (a[pos + 1] + 1,a[pos] - 1,-1);
else if(a[pos + 1] - 1 >= a[pos] + 1)
update (a[pos] + 1,a[pos + 1] - 1,-1);
if (a[pos + 1] + 1 <= val - 1)
update (a[pos + 1] + 1,val - 1,1);
else if(a[pos + 1] - 1 >= val + 1)
update (val + 1,a[pos + 1] - 1,1);
}
update (a[pos],a[pos],-1);
a[pos] = val;
update (a[pos],a[pos],1);
}
else {
scanf ("%lld", &val);
printf("%lld\n", get(val));
}
}
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:59:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld", &a[i]);
^
game.cpp:72:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld", &type);
^
game.cpp:75:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld%lld", &pos,&val);
^
game.cpp:105:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld", &val);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
103580 KB |
Output is correct |
| 2 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 5 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 6 |
Correct |
3 ms |
103580 KB |
Output is correct |
| 7 |
Correct |
0 ms |
103580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
103580 KB |
Output is correct |
| 2 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 5 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 6 |
Correct |
3 ms |
103580 KB |
Output is correct |
| 7 |
Correct |
0 ms |
103580 KB |
Output is correct |
| 8 |
Correct |
99 ms |
103580 KB |
Output is correct |
| 9 |
Correct |
253 ms |
103580 KB |
Output is correct |
| 10 |
Correct |
216 ms |
103580 KB |
Output is correct |
| 11 |
Correct |
79 ms |
103580 KB |
Output is correct |
| 12 |
Correct |
143 ms |
103580 KB |
Output is correct |
| 13 |
Correct |
186 ms |
103580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
103580 KB |
Output is correct |
| 2 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 3 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 4 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 5 |
Correct |
6 ms |
103580 KB |
Output is correct |
| 6 |
Correct |
3 ms |
103580 KB |
Output is correct |
| 7 |
Correct |
0 ms |
103580 KB |
Output is correct |
| 8 |
Correct |
99 ms |
103580 KB |
Output is correct |
| 9 |
Correct |
253 ms |
103580 KB |
Output is correct |
| 10 |
Correct |
216 ms |
103580 KB |
Output is correct |
| 11 |
Correct |
79 ms |
103580 KB |
Output is correct |
| 12 |
Correct |
143 ms |
103580 KB |
Output is correct |
| 13 |
Correct |
186 ms |
103580 KB |
Output is correct |
| 14 |
Correct |
409 ms |
103580 KB |
Output is correct |
| 15 |
Correct |
433 ms |
103580 KB |
Output is correct |
| 16 |
Correct |
509 ms |
103580 KB |
Output is correct |
| 17 |
Correct |
459 ms |
103580 KB |
Output is correct |
| 18 |
Correct |
456 ms |
103580 KB |
Output is correct |
