#include<bits/stdc++.h>
#define el '\n'
using namespace std;
int32_t main (){
// freopen("simple.inp" , "r" , stdin);
// freopen("simple.out" , "w" , stdout);
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];
// const int B = sqrt(m);
const int B = 800;
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));
}
}
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 = upper_bound(process.begin() , process.end() , make_pair(a , INT_MAX)) - process.begin();
if (it1 == (int)process.size()) continue;
auto it2 = upper_bound(process.begin() , process.end() , make_pair(b , INT_MIN)) - process.begin() - 1;
if (it1 > it2) continue;
if (process[it1].first > a && process[it2].first < b){
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[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]++;
}
};
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);
}
st.push(make_pair(x , h[x]));
h[x] = vl;
}
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:31: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]
31 | for (int j = 0 ; j < queries[i].size() ; j++){
| ~~^~~~~~~~~~~~~~~~~~~
game.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
32 | 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:38: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]
38 | assert(process.size() == cnt);
| ~~~~~~~~~~~~~~~^~~~~~
game.cpp:53: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]
53 | for (int j = 0 ; j < process.size() ; j++ ){
| ~~^~~~~~~~~~~~~~~~
game.cpp: In lambda function:
game.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | auto [pos , val] = st.top();
| ^
game.cpp: In function 'int32_t main()':
game.cpp:85:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for ( auto [type , pos , val] : queries[i] ){
| ^
game.cpp:91:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | auto [x , vl] = update[j];
| ^
game.cpp:105:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
105 | for ( auto [type , pos , val] : queries[i] ){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
294 ms |
2772 KB |
Output is correct |
| 9 |
Execution timed out |
1055 ms |
3272 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
348 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
294 ms |
2772 KB |
Output is correct |
| 9 |
Execution timed out |
1055 ms |
3272 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
