oj.uz

Submission #967612

# Submission time Handle Problem Language Result Execution time Memory
967612 2024-04-22T14:00:33 Z Yang8on Simple game (IZhO17_game) C++14
100 / 100
 50 ms 9052 KB 
#include <bits/stdc++.h>
#define Y8o "Simple game"
#define maxn 1000005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
    if(fopen(Y8o".inp", "r"))
    {
        freopen(Y8o".inp", "r", stdin);
//        freopen(Y8o".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

const int mx = maxn - 5;

int n, Q;
int a[maxn];

int bit[maxn];
void update(int x, int val) { while(x <= mx) bit[x] += val, x += (x & -x); }
int get(int x) { int best = 0; while(x) best += bit[x], x -= (x & -x); return best; }

void update(int l, int r, int val)
{
    if(l > r) swap(l, r);
    update(l, +val), update(r + 1, -val);
}

void solve()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    for(int i = 1; i <= n - 1; i ++)
        update(a[i], a[i + 1], +1);

    for(int i = 1, id, pos, H; i <= Q; i ++)
    {
        cin >> id;
        if(id == 1)
        {
            cin >> pos >> H;
            if(pos < n)
            {
                update(a[pos], a[pos + 1], -1);
                update(H, a[pos + 1], +1);
            }
            if(pos > 1)
            {
                update(a[pos - 1], a[pos], -1);
                update(H, a[pos - 1], +1);
            }
            a[pos] = H;
        }
        else
        {
            cin >> H;
            cout << get(H) << '\n';
        }
    }

}


int main()
{
    iof();

    int nTest = 1;
//    cin >> nTest;

    while(nTest --) {
        solve();
    }

    ctime();
    return 0;
}

Compilation message

game.cpp: In function 'void iof()':
game.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4760 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4760 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 30 ms 7388 KB Output is correct
9 Correct 38 ms 9052 KB Output is correct
10 Correct 31 ms 8784 KB Output is correct
11 Correct 29 ms 7516 KB Output is correct
12 Correct 31 ms 8528 KB Output is correct
13 Correct 31 ms 8532 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 1 ms 4696 KB Output is correct
5 Correct 1 ms 4760 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 30 ms 7388 KB Output is correct
9 Correct 38 ms 9052 KB Output is correct
10 Correct 31 ms 8784 KB Output is correct
11 Correct 29 ms 7516 KB Output is correct
12 Correct 31 ms 8528 KB Output is correct
13 Correct 31 ms 8532 KB Output is correct
14 Correct 41 ms 8788 KB Output is correct
15 Correct 50 ms 8996 KB Output is correct
16 Correct 49 ms 8768 KB Output is correct
17 Correct 39 ms 8796 KB Output is correct
18 Correct 42 ms 8784 KB Output is correct