#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cmath>
#include <queue>
#include <bitset>
#include <numeric>
#include <array>
#include <cstring>
#include <random>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e6 + 42, H = 1e6 + 42;
int t[N];
void update (int v, int tl, int tr, int l, int r, int add) {
if (l > r)
return;
if (l == tl && tr == r)
t[v] += add;
else {
int tm = (tl + tr) / 2;
update (v*2, tl, tm, l, min(r,tm), add);
update (v*2+1, tm+1, tr, max(l,tm+1), r, add);
}
}
int get (int v, int tl, int tr, int pos) {
if (tl == tr)
return t[v];
int tm = (tl + tr) / 2;
if (pos <= tm)
return t[v] + get (v*2, tl, tm, pos);
else
return t[v] + get (v*2+1, tm+1, tr, pos);
}
int n, m;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
vector<int> h(n);
for(int i = 0; i < n; i++) {
cin >> h[i];
if(i) {
update(1, 0, H - 1, min(h[i], h[i - 1]), max(h[i], h[i - 1]), 1);
}
}
map<int, int> amm;
for(int i = 1; i < n - 1; i++) amm[h[i]]++;
while(m--) {
int t; cin >> t;
if(t == 2) {
int ch; cin >> ch;
cout << get(1, 0, H - 1, ch) - amm[ch] << '\n';
} else {
int ci, ch; cin >> ci >> ch;
ci--;
if(ci > 0 && ci < n - 1) amm[h[ci]]--;
if(ci + 1 < n) {
update(1, 0, H - 1, min(h[ci], h[ci + 1]), max(h[ci], h[ci + 1]), -1);
}
if(ci - 1 >= 0) {
update(1, 0, H - 1, min(h[ci], h[ci - 1]), max(h[ci], h[ci - 1]), -1);
}
h[ci] = ch;
if(ci + 1 < n) {
update(1, 0, H - 1, min(h[ci], h[ci + 1]), max(h[ci], h[ci + 1]), 1);
}
if(ci - 1 >= 0) {
update(1, 0, H - 1, min(h[ci], h[ci - 1]), max(h[ci], h[ci - 1]), 1);
}
if(ci > 0 && ci < n - 1) amm[h[ci]]++;
}
}
return 0;
}
/*
*/
Compilation message
game.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
6636 KB |
Output is correct |
3 |
Correct |
6 ms |
6508 KB |
Output is correct |
4 |
Correct |
7 ms |
6764 KB |
Output is correct |
5 |
Correct |
7 ms |
6636 KB |
Output is correct |
6 |
Correct |
7 ms |
6764 KB |
Output is correct |
7 |
Correct |
3 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
6636 KB |
Output is correct |
3 |
Correct |
6 ms |
6508 KB |
Output is correct |
4 |
Correct |
7 ms |
6764 KB |
Output is correct |
5 |
Correct |
7 ms |
6636 KB |
Output is correct |
6 |
Correct |
7 ms |
6764 KB |
Output is correct |
7 |
Correct |
3 ms |
492 KB |
Output is correct |
8 |
Correct |
53 ms |
1772 KB |
Output is correct |
9 |
Correct |
260 ms |
20256 KB |
Output is correct |
10 |
Correct |
250 ms |
20136 KB |
Output is correct |
11 |
Correct |
46 ms |
1644 KB |
Output is correct |
12 |
Correct |
126 ms |
4460 KB |
Output is correct |
13 |
Correct |
130 ms |
7404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
6 ms |
6636 KB |
Output is correct |
3 |
Correct |
6 ms |
6508 KB |
Output is correct |
4 |
Correct |
7 ms |
6764 KB |
Output is correct |
5 |
Correct |
7 ms |
6636 KB |
Output is correct |
6 |
Correct |
7 ms |
6764 KB |
Output is correct |
7 |
Correct |
3 ms |
492 KB |
Output is correct |
8 |
Correct |
53 ms |
1772 KB |
Output is correct |
9 |
Correct |
260 ms |
20256 KB |
Output is correct |
10 |
Correct |
250 ms |
20136 KB |
Output is correct |
11 |
Correct |
46 ms |
1644 KB |
Output is correct |
12 |
Correct |
126 ms |
4460 KB |
Output is correct |
13 |
Correct |
130 ms |
7404 KB |
Output is correct |
14 |
Correct |
394 ms |
19948 KB |
Output is correct |
15 |
Correct |
399 ms |
19948 KB |
Output is correct |
16 |
Correct |
408 ms |
20076 KB |
Output is correct |
17 |
Correct |
405 ms |
19948 KB |
Output is correct |
18 |
Correct |
389 ms |
19948 KB |
Output is correct |