#include <bits/stdc++.h>
#define Y8o "Simple game"
#define maxn 1000005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
if(fopen(Y8o".inp", "r"))
{
freopen(Y8o".inp", "r", stdin);
// freopen(Y8o".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
const int mx = maxn - 5;
int n, Q;
int a[maxn];
int bit[maxn];
void update(int x, int val) { while(x <= mx) bit[x] += val, x += (x & -x); }
int get(int x) { int best = 0; while(x) best += bit[x], x -= (x & -x); return best; }
void update(int l, int r, int val)
{
if(l > r) swap(l, r);
update(l, +val), update(r + 1, -val);
}
void solve()
{
cin >> n >> Q;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n - 1; i ++)
update(a[i], a[i + 1], +1);
for(int i = 1, id, pos, H; i <= Q; i ++)
{
cin >> id;
if(id == 1)
{
cin >> pos >> H;
if(pos < n)
{
update(a[pos], a[pos + 1], -1);
update(H, a[pos + 1], +1);
}
if(pos > 1)
{
update(a[pos - 1], a[pos], -1);
update(H, a[pos - 1], +1);
}
a[pos] = H;
}
else
{
cin >> H;
cout << get(H) << '\n';
}
}
}
int main()
{
iof();
int nTest = 1;
// cin >> nTest;
while(nTest --) {
solve();
}
ctime();
return 0;
}
Compilation message
game.cpp: In function 'void iof()':
game.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(Y8o".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4564 KB |
Output is correct |
3 |
Correct |
2 ms |
4696 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4760 KB |
Output is correct |
6 |
Correct |
2 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4564 KB |
Output is correct |
3 |
Correct |
2 ms |
4696 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4760 KB |
Output is correct |
6 |
Correct |
2 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
30 ms |
7388 KB |
Output is correct |
9 |
Correct |
38 ms |
9052 KB |
Output is correct |
10 |
Correct |
31 ms |
8784 KB |
Output is correct |
11 |
Correct |
29 ms |
7516 KB |
Output is correct |
12 |
Correct |
31 ms |
8528 KB |
Output is correct |
13 |
Correct |
31 ms |
8532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4564 KB |
Output is correct |
3 |
Correct |
2 ms |
4696 KB |
Output is correct |
4 |
Correct |
1 ms |
4696 KB |
Output is correct |
5 |
Correct |
1 ms |
4760 KB |
Output is correct |
6 |
Correct |
2 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
30 ms |
7388 KB |
Output is correct |
9 |
Correct |
38 ms |
9052 KB |
Output is correct |
10 |
Correct |
31 ms |
8784 KB |
Output is correct |
11 |
Correct |
29 ms |
7516 KB |
Output is correct |
12 |
Correct |
31 ms |
8528 KB |
Output is correct |
13 |
Correct |
31 ms |
8532 KB |
Output is correct |
14 |
Correct |
41 ms |
8788 KB |
Output is correct |
15 |
Correct |
50 ms |
8996 KB |
Output is correct |
16 |
Correct |
49 ms |
8768 KB |
Output is correct |
17 |
Correct |
39 ms |
8796 KB |
Output is correct |
18 |
Correct |
42 ms |
8784 KB |
Output is correct |