Submission #93567

#	Time	Username	Problem	Language	Result	Execution time	Memory
93567		Turysbek	Simple game (IZhO17_game)	C++14	100 / 100	200 ms	11388 KiB

game

// In the Name of God

#include <bits/stdc++.h>

using namespace std;

#define	ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(v) v.begin(), v.end()
#define bpc(v) __builtin_popcountll(v)
#define itr iterator
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; --i)
#define ub upper_bound
#define lb lower_bound

const int N = 1e5 + 5;
const int mod = 1e8 + 7;
const int inf = 1e6 + 1;
const double eps = 1e-15;
const int pw = 257;

int n, m, a[N], t[inf * 4];

void upd(int v, int l, int r, int L, int R, int val) {
    if (L > R)
        swap(L, R);
    if (L > r || l > R)
        return;
    if (L <= l && r <= R) {
        t[v] += val;
        return;
    }
    int mid = (l + r) >> 1;
    upd(v + v, l, mid, L, R, val);
    upd(v + v + 1, mid + 1, r, L, R, val);
}

int get(int v, int l, int r, int pos) {
    if (l == r)
        return t[v];
    int mid = (l + r) >> 1;
    if (pos <= mid)
        return t[v] + get(v + v, l, mid, pos);
    else
        return t[v] + get(v + v + 1, mid + 1, r, pos);
}

int main() {
	#ifdef Madi
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	#endif

	ios_base :: sync_with_stdio(false); cin.tie(NULL);

    cin >> n >> m;
    rep(i, 1, n) {
        cin >> a[i];
        if (i > 1)
            upd(1, 1, inf, a[i - 1], a[i], 1);
    }

    rep(i, 1, m) {
        int type;
        cin >> type;
        if (type == 1) {
            int pos, val;
            cin >> pos >> val;

            if (pos > 1)
                upd(1, 1, inf, a[pos - 1], a[pos], -1);
            if (pos < n)
                upd(1, 1, inf, a[pos + 1], a[pos], -1);

            a[pos] = val;
            if (pos > 1)
                upd(1, 1, inf, a[pos - 1], a[pos], 1);
            if (pos < n)
                upd(1, 1, inf, a[pos + 1], a[pos], 1);
        }
        else {
            int x;
            cin >> x;
            cout << get(1, 1, inf, x) << "\n";
        }
    }

	#ifdef Madi
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
	return 0;
}

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