Submission #377313

#	Time	Username	Problem	Language	Result	Execution time	Memory
377313		ijxjdjd	Simple game (IZhO17_game)	C++14	100 / 100	238 ms	11372 KiB

game

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXH = (int)(1e6) + 5;

int lzy[4*MAXH];
void upd(int l, int r, int val, int n=1, int tl=0, int tr=MAXH-1) {
    if (l > r) {
        swap(l, r);
    }
    if (l > tr || r < tl) {
        return;
    }
    else if (l <= tl && tr <= r) {
        lzy[n] += val;
    }
    else {
        int tm = (tl + tr)/2;
        upd(l, r, val, 2*n, tl, tm);
        upd(l, r, val, 2*n+1, tm+1, tr);
    }
}
int get(int i, int n=1, int tl=0,int tr=MAXH-1) {
    if (tl == tr) {
        return lzy[n];
    }
    int tm = (tl + tr)/2;
    if (i <= tm) {
        return lzy[n] + get(i, 2*n, tl, tm);
    }
    else {
        return lzy[n] + get(i, 2*n+1, tm+1, tr);
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M;
	cin >> N >> M;
	vector<int> v(N);
	FR(i, N) {
        cin >> v[i];
	}
    for (int i = 1; i < N; i++) {
        upd(v[i-1], v[i], 1);
    }
    FR(iter, M) {
        int id;
        cin >> id;
        if (id == 1) {
            int p, val;
            cin >> p >> val;
            p--;
            if (p > 0) {
                upd(v[p-1], v[p], -1);
                upd(v[p-1], val, 1);
            }
            if (p < N-1) {
                upd(v[p], v[p+1], -1);
                upd(val, v[p+1], 1);
            }
            v[p] = val;
        }
        else {
            int H;
            cin >> H;
            cout << get(H) << '\n';
        }
    }
	return 0;
}

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