#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5+7;
int t[2*MAXN];
int ina[MAXN];
int n;
map<int,int> key;
void update(int l, int r, int v){
for (l+=n, r+=n+1; l<r; l>>=1, r>>=1){
if (l&1) t[l++] += v;
if (r&1) t[--r] += v;
}
}
int ans(int ind){
int res = 0;
for (int i=ind+n; i>0; i>>=1) res+=t[i];
return res;
}
signed main(){
int m; cin>>n>>m;
vector<int> values;
vector<tuple<int,int,int>> queries(m);
for (int i=0; i<n; i++) cin>>ina[i];
for (int i=0; i<n; i++) values.push_back(ina[i]);
for (int i=0; i<m; i++){
int r; cin>>r;
if (r==1){
int a,b; cin>>a>>b; a--; values.push_back(b); queries[i] = {1,a,b};
} else {
int k; cin>>k; values.push_back(k); queries[i] = {2,k,0};
}
}
sort(values.begin(), values.end());
int ind = 0;
for (int i=0; i<values.size(); i++){
if (key.count(values[i])) continue;
key[values[i]] = ind++;
}
for (int i=0; i<n; i++) ina[i] = key[ina[i]];
for (int i=0; i<m; i++){
int r = get<0> (queries[i]);
if (r==1){
get<2> (queries[i]) = key[get<2> (queries[i])];
} else {
get<1> (queries[i]) = key[get<1> (queries[i])];
}
}
// for (int i=0; i<n; i++) cout<<ina[i]<<' '; cout<<'\n';
// for (auto [a,b,c]: queries){
// if (a==1) {
// cout<<b<<' '<<c<<'\n';
// } else {
// cout<<b<<'\n';
// }
// }
for (int i=0; i<n-1; i++){
update(min(ina[i], ina[i+1]), max(ina[i],ina[i+1]), 1);
}
for (auto [a,b,c]: queries){
if (a==1){
if (b){
update(min(ina[b], ina[b-1]), max(ina[b], ina[b-1]), -1);
update(min(ina[b-1], c), max(ina[b-1], c), 1);
}
if (b!=n-1){
update(min(ina[b], ina[b+1]), max(ina[b], ina[b+1]), -1);
update(min(ina[b+1], c), max(ina[b+1], c), 1);
}
ina[b] = c;
} else {
cout<<ans(b)<<'\n';
}
}
}
Compilation message
game.cpp: In function 'int main()':
game.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i=0; i<values.size(); i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2652 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
