#include<bits/stdc++.h>
#define INF 1e9
#define fi first
#define se second
#define FOR(i, k, n) for(int i = k; i <= n; i++)
#define FOR1(i, k, n) for(int i = k; i >= n; i--)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int, int>
#define vii vector<pii>
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define re return 0
#define mii map<int, int>
#define input "DANCE.inp"
#define output "DANCE.out"
#define rf freopen(input, "r", stdin); freopen(output, "w", stdout)
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int a[maxn];
int lazy[maxn * 4], T[maxn * 4];
void fix(int id, int l, int r)
{
if(l == r || fix[id] == 0)
return;
lazy[id * 2] += lazy[id];
lazy[id * 2 + 1] += lazy[id];
T[id * 2] += lazy[id];
T[id * 2 + 1] += lazy[id];
lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val)
{
if(l > v | r < u)
return;
if(l >= u && r <= v)
{
T[id] += val;
lazy[id] += val;
return;
}
fix(id, l, r);
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, val);
update(id * 2 + 1, mid + 1, r, u, v, val);
}
int get(int id, int l, int r, int pos)
{
if(l == r)
return T[id];
fix(id, l, r);
int mid = (l + r) / 2;
if(pos <= mid)
return get(id * 2, l, mid, pos);
return get(id * 2 + 1, mid + 1, r, pos);
}
int main()
{
fastio;
int n, m;
cin >> n >> m;
int maxx = 0;
FOR(i, 1, n)
cin >> a[i];
FOR(i, 2, n)
{
update(1, 1, 1000000, min(a[i - 1], a[i]), max(a[i], a[i - 1]), 1);
if(i != n)
update(1, 1, 1000000, a[i], a[i], -1);
}
while(m--)
{
int op;
cin >> op;
if(op == 1)
{
int pos, val;
cin >> pos >> val;
if(pos > 1)
{
update(1, 1, 1000000, min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]), -1);
update(1, 1, 1000000, min(a[pos - 1], val), max(a[pos - 1], val), 1);
}
if(pos < n)
{
update(1, 1, 1000000, min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]), -1);
update(1, 1, 1000000, min(val, a[pos + 1]), max(val, a[pos + 1]), 1);
}
if(pos != 1 && pos != n)
{
update(1, 1, 1000000, a[pos], a[pos], 1);
update(1, 1, 1000000, val, val, -1);
}
}
else
{
int pos;
cin >> pos;
cout << get(1, 1, 1000000, pos) << "\n";
}
}
re;
}
Compilation message
game.cpp: In function 'void fix(int, int, int)':
game.cpp:27:21: warning: pointer to a function used in arithmetic [-Wpointer-arith]
27 | if(l == r || fix[id] == 0)
| ^
game.cpp: In function 'void update(int, int, int, int, int, int)':
game.cpp:37:7: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
37 | if(l > v | r < u)
| ~~^~~
game.cpp: In function 'int main()':
game.cpp:65:6: warning: unused variable 'maxx' [-Wunused-variable]
65 | int maxx = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
20060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
