Submission #967590

#	Time	Username	Problem	Language	Result	Execution time	Memory
967590		Yang8on	Simple game (IZhO17_game)	C++14	0 / 100	5 ms	19036 KiB

game

#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];
struct dl { int val, lazy; } st[4 * maxn];

void down(int id)
{
    ll t = st[id].lazy;

    st[id * 2].val += t, st[id * 2].lazy += t;
    st[id * 2 + 1].val += t, st[id * 2 + 1].val += t;

    st[id].lazy = 0;
}

void update(int u, int v, int val, int id = 1, int l = 1, int r = mx)
{
    if(v < l || r < u) return ;
    if(u <= l && r <= v) {
        st[id].val += val;
        st[id].lazy += val;
        return ;
    }

    int mid = (l + r) >> 1;
    down(id);

    update(u, v, val, id * 2, l, mid);
    update(u, v, val, id * 2 + 1, mid + 1, r);

    st[id].val = st[id * 2].val + st[id * 2 + 1].val;
}

int get(int i, int id = 1, int l = 1, int r = mx)
{
    if(i < l || r < i) return 0;
    if(l == r) return st[id].val;

    int mid = (l + r) >> 1;
    down(id);

    return get(i, id * 2, l, mid) + get(i, id * 2 + 1, mid + 1, r);
}

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

    for(int i = 1; i <= n - 1; i ++)
    {
        int mi = min(a[i], a[i + 1]), ma = max(a[i], a[i + 1]);
        if(mi + 1 <= ma - 1) update(mi + 1, ma - 1, +1);
    }

    for(int i = 1, id, pos, H; i <= n; i ++)
    {
        cin >> id;

        if(id == 1)
        {
            cin >> pos >> H;

            if(pos < n)
            {
                int mi = min(a[pos], a[pos + 1]), ma = max(a[pos], a[pos + 1]);
                if(mi + 1 <= ma - 1) update(mi + 1, ma - 1, -1);

                mi = min(H, a[pos + 1]), ma = max(H, a[pos + 1]);
                if(mi + 1 <= ma - 1) update(mi + 1, ma - 1, +1);
            }

            if(pos >= 2)
            {
                int mi = min(a[pos], a[pos - 1]), ma = max(a[pos], a[pos - 1]);
                if(mi + 1 <= ma - 1) update(mi + 1, ma - 1, -1);

                mi = min(H, a[pos - 1]), ma = max(H, a[pos - 1]);
                if(mi + 1 <= ma - 1) update(mi + 1, ma - 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 (stderr)

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: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51