#include<bits/stdc++.h>
#define el '\n'
using namespace std;
const int B = 320;
int32_t main (){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n , m;
cin >> n >> m;
vector<int> h(n + 5);
for (int i = 1 ; i <= n ; i++) cin >> h[i];
vector<vector<tuple<int , int , int>>> queries(m / B + 5);
for (int i = 1 ; i <= m ; i++){
int type , pos , val;
cin >> type >> pos;
if (type == 1){
cin >> val;
queries[i / B].push_back(make_tuple(type , pos , val));
}
else {
queries[i / B].push_back(make_tuple(type , pos , -1));
}
}
cout << el;
for (int i = 0 ; i <= m / B ; i++){
vector<pair<int , int>> process;
int cnt = 0;
for (int j = 0 ; j < queries[i].size() ; j++){
auto [type , pos , val] = queries[i][j];
if (type == 2){
process.push_back(make_pair(pos , cnt++));
}
}
sort(process.begin() , process.end());
assert(process.size() == cnt);
vector<int> diff(n + 5);
for (int j = 1 ; j < n ; j++){
int a = h[j] , b = h[j + 1];
if (a > b) swap(a , b);
auto it1 = lower_bound(process.begin() , process.end() , make_pair(a , INT_MIN)) - process.begin();
if (it1 == (int)process.size()) continue;
auto it2 = upper_bound(process.begin() , process.end() , make_pair(b , INT_MIN)) - process.begin() - 1;
diff[it1]++;
diff[it2 + 1]--;
}
vector<int> ans(B + 10);
for (int j = 0 ; j < process.size() ; j++ ){
if (!j){
ans[process[j].second] = diff[j];
continue;
}
diff[j] += diff[j - 1];
ans[process[j].second] = diff[j];
}
cnt = 0;
vector<pair<int , int>> update;
stack<pair<int , int>> st;
auto roll_back = [&]() -> void {
while (!st.empty()){
auto [pos , val] = st.top();
h[pos] = val;
st.pop();
}
};
auto modify = [&](int x , int nex , int H , int new_val , int id) -> void{
if (h[x] < H){
if (h[nex] > H && new_val > H) ans[id]--;
else if (h[nex] < H && new_val > H) ans[id]++;
}
else {
if (h[nex] < H && new_val < H) ans[id]--;
else if (h[nex] > H && new_val < H) ans[id]++;
}
st.push(make_pair(x , h[x]));
h[x] = new_val;
};
for ( auto [type , pos , val] : queries[i] ){
if (type == 1) update.push_back(make_pair(pos , val));
else {
roll_back();
int H = pos;
for (int j = 0 ; j < (int)update.size() ; j++){
auto [x , vl] = update[j];
if (x == 1) modify(x , x + 1 , H , vl , cnt);
else if (x == n) modify(x , x - 1 , H , vl , cnt);
else {
modify(x , x - 1 , H , vl , cnt);
modify(x , x + 1 , H , vl , cnt);
}
}
cnt++;
}
}
cnt = 0;
for ( auto [type , pos , val] : queries[i] ){
if (type == 1) h[pos] = val;
else cout << ans[cnt++] << el;
}
}
}
Compilation message
game.cpp: In function 'int32_t main()':
game.cpp:30:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int j = 0 ; j < queries[i].size() ; j++){
| ~~^~~~~~~~~~~~~~~~~~~
game.cpp:31:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [type , pos , val] = queries[i][j];
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from game.cpp:1:
game.cpp:37:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | assert(process.size() == cnt);
| ~~~~~~~~~~~~~~~^~~~~~
game.cpp:49:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int j = 0 ; j < process.size() ; j++ ){
| ~~^~~~~~~~~~~~~~~~
game.cpp: In lambda function:
game.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | auto [pos , val] = st.top();
| ^
game.cpp: In function 'int32_t main()':
game.cpp:79:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | for ( auto [type , pos , val] : queries[i] ){
| ^
game.cpp:85:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [x , vl] = update[j];
| ^
game.cpp:97:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for ( auto [type , pos , val] : queries[i] ){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
