oj.uz

Submission #1009672

# Submission time Handle Problem Language Result Execution time Memory
1009672 2024-06-27T19:33:56 Z nguyennh Simple game (IZhO17_game) C++14
22 / 100
 1000 ms 4160 KB 
#include<bits/stdc++.h>
#define el '\n'
using namespace std;

const int B = 800;
const int MN = 1e5 + 5;

vector<tuple<int , int , int>> queries[MN / B + 5];
vector<pair<int , int>> q2[MN / B + 5];

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];
  int cnt = 0;
  for (int i = 1 ; i <= m ; i++){
    if (i % B == 0) cnt = 0;
    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));
      q2[i / B].push_back(make_pair(pos , cnt++));
    }
  }
  for (int i = 0 ; i <= m / B ; i++) sort(q2[i].begin() , q2[i].end()); 
  for (int i = 0 ; i <= m / B ; i++){
    int cnt = 0;
    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(q2[i].begin() , q2[i].end() , make_pair(a , INT_MAX)) - q2[i].begin();
      if (it1 == (int)q2[i].size()) continue;
      auto it2 = upper_bound(q2[i].begin() , q2[i].end() , make_pair(b , INT_MIN)) - q2[i].begin() - 1;
      if (it1 > it2) continue;
      if (q2[i][it1].first > a && q2[i][it2].first < b){
        diff[it1]++;
        diff[it2 + 1]--;
      }
    }
    vector<int> ans(B + 10);
    for (int j = 0 ; j < q2[i].size() ; j++ ){
      if (!j){
        ans[q2[i][j].second] = diff[j];
        continue;
      }
      diff[j] += diff[j - 1];
      ans[q2[i][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:51: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]
   51 |     for (int j = 0 ; j < q2[i].size() ; j++ ){
      |                      ~~^~~~~~~~~~~~~~
game.cpp: In lambda function:
game.cpp:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         auto [pos , val] = st.top();
      |              ^
game.cpp: In function 'int32_t main()':
game.cpp:83:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for ( auto [type , pos , val] : queries[i] ){
      |                ^
game.cpp:89:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |           auto [x , vl] = update[j];
      |                ^
game.cpp:103:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |     for ( auto [type , pos , val] : queries[i] ){
      |                ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 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 0 ms 348 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 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 0 ms 348 KB Output is correct
8 Correct 325 ms 3792 KB Output is correct
9 Execution timed out 1031 ms 4160 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 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 0 ms 348 KB Output is correct
8 Correct 325 ms 3792 KB Output is correct
9 Execution timed out 1031 ms 4160 KB Time limit exceeded
10 Halted 0 ms 0 KB -