Submission #204758

#	Time	Username	Problem	Language	Result	Execution time	Memory
204758		quocnguyen1012	Simple game (IZhO17_game)	C++14	100 / 100	101 ms	6904 KiB

game

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

class fenwick_tree
{
  vector<int> cnt; int n;
public:
  fenwick_tree(int _n)
  {
    n = _n;
    cnt.assign(n + 5, 0);
  }
  void upd(int i, int v)
  {
    for (; i <= n; i += i & -i)
      cnt[i] += v;
  }
  int sum(int i)
  {
    int res = 0;
    for (; i; i -= i & -i)
      res += cnt[i];
    return res;
  }
  void rupd(int l, int r, int v)
  {
    if (l > r) swap(l, r);
    upd(l, v); upd(r + 1, -v);
  }
};

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  fenwick_tree ft(1e6);
  int N, M; cin >> N >> M;
  vector<int> a(N + 5);
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    if (i > 1) ft.rupd(a[i - 1], a[i], 1);
  }
  while (M--){
    int type; cin >> type;
    if (type == 1){
      int i, val; cin >> i >> val;
      if (i > 1) ft.rupd(a[i - 1], a[i], -1);
      if (i < N) ft.rupd(a[i], a[i + 1], -1);
      a[i] = val;
      if (i > 1) ft.rupd(a[i - 1], a[i], 1);
      if (i < N) ft.rupd(a[i], a[i + 1], 1);
    }
    else{
      int h; cin >> h;
      cout << ft.sum(h) << '\n';
    }
  }
}

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
game.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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