oj.uz

Submission #390414

# Submission time Handle Problem Language Result Execution time Memory
390414 2021-04-16T03:58:35 Z acm Simple game (IZhO17_game) C++14
100 / 100
 74 ms 6928 KB 
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define precision     \
  cout.precision(30); \
  cerr.precision(10);
#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define pii pair<int, int>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) for (int i = l; i != r; (l > r ? i-- : i++))
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define all(x) x.begin(), x.end()
#define pc(x) __builtin_popcount(x)
#define pcll(x) __builtin_popcountll(x)
#define F first
#define S second
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void ioi(string name) {
  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}
int n, q, a[1000005], b[1000005];
void upd(int x, int y) {
  for (; x <= 1000000; x += (x & -x)) b[x] += y;
}
int get(int x) {
  int y = 0;
  for (; x > 0; x -= (x & -x)) y += b[x];
  return y;
}
int main() {
  speed;
  precision;
  // code
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (i > 1) {
      upd(min(a[i - 1], a[i]), 1);
      upd(max(a[i - 1], a[i]) + 1, -1);
    }
  }
  while (q--) {
    int type, x, y;
    cin >> type;
    if (type == 1) {
      cin >> x >> y;
      if (x > 1) {
        upd(min(a[x - 1], a[x]), -1);
        upd(max(a[x - 1], a[x]) + 1, 1);
      }
      if (x < n) {
        upd(min(a[x], a[x + 1]), -1);
        upd(max(a[x], a[x + 1]) + 1, 1);
      }
      a[x] = y;
      if (x > 1) {
        upd(min(a[x - 1], a[x]), 1);
        upd(max(a[x - 1], a[x]) + 1, -1);
      }
      if (x < n) {
        upd(min(a[x], a[x + 1]), 1);
        upd(max(a[x], a[x + 1]) + 1, -1);
      }
    }
    if (type == 2) {
      cin >> x;
      cout << get(x) << " ";
    }
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Compilation message

game.cpp: In function 'void ioi(std::string)':
game.cpp:26:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   27 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 2 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 39 ms 944 KB Output is correct
9 Correct 51 ms 5884 KB Output is correct
10 Correct 51 ms 6744 KB Output is correct
11 Correct 40 ms 1584 KB Output is correct
12 Correct 47 ms 2884 KB Output is correct
13 Correct 43 ms 2812 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 39 ms 944 KB Output is correct
9 Correct 51 ms 5884 KB Output is correct
10 Correct 51 ms 6744 KB Output is correct
11 Correct 40 ms 1584 KB Output is correct
12 Correct 47 ms 2884 KB Output is correct
13 Correct 43 ms 2812 KB Output is correct
14 Correct 71 ms 6816 KB Output is correct
15 Correct 64 ms 6852 KB Output is correct
16 Correct 67 ms 6844 KB Output is correct
17 Correct 74 ms 6928 KB Output is correct
18 Correct 63 ms 6740 KB Output is correct