Submission #1009666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009666		nguyennh	Simple game (IZhO17_game)	C++14	22 / 100	1066 ms	5068 KiB

game

#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 = 320;
  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 (stderr)

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] ){
      |                ^

• Subtask 1: 22 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51