Submission #1280806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280806		vuquangsang	Simple game (IZhO17_game)	C++20	100 / 100	37 ms	5284 KiB

game

#include <bits/stdc++.h>
using namespace std;


struct FenwickTree
{
    int n;
    vector<int> bit;
    FenwickTree(int _n)
    {
        n = _n;
        bit.resize(n + 2);
    }

    void upd(int x, int v)
    {
        for(; x <= n; x += x & -x) bit[x] += v;
    }
    void update(int l, int r, int x)
    {
        upd(l, x);
        upd(r + 1, -x);
    }
    int get(int x)
    {
        int ans = 0;
        for(; x >= 1; x -= x & -x) ans += bit[x];
        return ans;
    }
};
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define soicodoc "game"
    if(fopen(soicodoc".INP", "r")) {
        freopen(soicodoc".INP", "r", stdin);
        freopen(soicodoc".OUT", "w", stdout);
    }

    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    const int N = 1e6 + 2;

    FenwickTree bit(N);

    for(int i = 1; i < n; i++) {
        bit.update(min(a[i], a[i + 1]), max(a[i], a[i + 1]), 1);
    }

    while(q--) {
        int type; cin >> type;
        if(type == 1) {
            int i, val; cin >> i >> val;
            if(i > 1) bit.update(min(a[i - 1], a[i]), max(a[i - 1], a[i]), -1);
            if(i < n) bit.update( min(a[i], a[i + 1]), max(a[i], a[i + 1]), -1);

            a[i] = val;

            if(i > 1) bit.update(min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
            if(i < n) bit.update(min(a[i], a[i + 1]), max(a[i], a[i + 1]), 1);
        }
        else {
            int H; cin >> H;
            cout << bit.get(H) << "\n";
        }
    }

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

game.cpp:31:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   31 | main()
      | ^~~~
game.cpp: In function 'int main()':
game.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(soicodoc".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(soicodoc".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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