oj.uz

Submission #204758

# Submission time Handle Problem Language Result Execution time Memory
204758 2020-02-27T03:27:13 Z quocnguyen1012 Simple game (IZhO17_game) C++14
100 / 100
 101 ms 6904 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 9 ms 4216 KB Output is correct
6 Correct 9 ms 4344 KB Output is correct
7 Correct 8 ms 4216 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 9 ms 4216 KB Output is correct
6 Correct 9 ms 4344 KB Output is correct
7 Correct 8 ms 4216 KB Output is correct
8 Correct 48 ms 5624 KB Output is correct
9 Correct 89 ms 6904 KB Output is correct
10 Correct 72 ms 6904 KB Output is correct
11 Correct 46 ms 5500 KB Output is correct
12 Correct 55 ms 6704 KB Output is correct
13 Correct 60 ms 6776 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4216 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 9 ms 4216 KB Output is correct
6 Correct 9 ms 4344 KB Output is correct
7 Correct 8 ms 4216 KB Output is correct
8 Correct 48 ms 5624 KB Output is correct
9 Correct 89 ms 6904 KB Output is correct
10 Correct 72 ms 6904 KB Output is correct
11 Correct 46 ms 5500 KB Output is correct
12 Correct 55 ms 6704 KB Output is correct
13 Correct 60 ms 6776 KB Output is correct
14 Correct 93 ms 6904 KB Output is correct
15 Correct 90 ms 6904 KB Output is correct
16 Correct 101 ms 6904 KB Output is correct
17 Correct 91 ms 6904 KB Output is correct
18 Correct 92 ms 6904 KB Output is correct