Submission #879504

#	Time	Username	Problem	Language	Result	Execution time	Memory
879504		sleepntsheep	Simple game (IZhO17_game)	C++17	100 / 100	42 ms	6944 KiB

game

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 100000

int n, m, h[100000], t[1000001];

void upd(int p, int k) { for (; p < sizeof t / sizeof *t; p+=p&-p) t[p]+=k; }
int qry(int p) { int z{0}; for(; p;p-=p&-p)z+=t[p];return z; }

void cal(int i, int k)
{
    if (h[i] > h[i-1]) upd(h[i-1]+1, k), upd(h[i]+1, -k);
    else if (h[i] < h[i-1]) upd(h[i]+1, k), upd(h[i-1]+1, -k);
}

int main()
{
    ShinLena;
    cin >> n >> m >> h[0];
    for (int i = 1; i < n; ++i) cin >> h[i], cal(i, 1);

    for (int t, x, y; m--;)
    {
        cin >> t >> x;
        if (t == 1)
        {
            --x; cin >> y;
            if (x) cal(x, -1);
            if (x + 1 < n) cal(x+1, -1);
            h[x] = y;
            if (x) cal(x, 1);
            if (x + 1 < n) cal(x+1, 1);
        }
        else
        {
            cout << qry(x) << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

game.cpp: In function 'void upd(int, int)':
game.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   28 | void upd(int p, int k) { for (; p < sizeof t / sizeof *t; p+=p&-p) t[p]+=k; }
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~

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