oj.uz

Submission #967613

# Submission time Handle Problem Language Result Execution time Memory
967613 2024-04-22T14:02:09 Z vjudge1 Simple game (IZhO17_game) C++17
100 / 100
 50 ms 7356 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 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 33 ms 6744 KB Output is correct
9 Correct 31 ms 7356 KB Output is correct
10 Correct 32 ms 7248 KB Output is correct
11 Correct 31 ms 6736 KB Output is correct
12 Correct 29 ms 7248 KB Output is correct
13 Correct 31 ms 7156 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 33 ms 6744 KB Output is correct
9 Correct 31 ms 7356 KB Output is correct
10 Correct 32 ms 7248 KB Output is correct
11 Correct 31 ms 6736 KB Output is correct
12 Correct 29 ms 7248 KB Output is correct
13 Correct 31 ms 7156 KB Output is correct
14 Correct 41 ms 7004 KB Output is correct
15 Correct 50 ms 7004 KB Output is correct
16 Correct 41 ms 6868 KB Output is correct
17 Correct 39 ms 7004 KB Output is correct
18 Correct 38 ms 7004 KB Output is correct