Submission #157029

#	Time	Username	Problem	Language	Result	Execution time	Memory
157029		maruii	Employment (JOI16_employment)	C++14	100 / 100	267 ms	12904 KiB

employment

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

const int SIZE = 1 << 19;
struct ST {
	int A[2 * SIZE];
	void update(int s, int e, int v) {
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) A[s++] += v;
			if (~e & 1) A[e--] += v;
		}
	}
	int query(int x) {
		int ret = 0;
		for (x += SIZE; x; x >>= 1) ret += A[x];
		return ret;
	}
} seg;

struct In {
	int q, x, y;
} in[200005];

int A[200005];
vector<int> xx(1);

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M; cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i];
		xx.push_back(A[i]);
	}
	for (int i = 0; i < M; ++i) {
		int q, x, y = 0; cin >> q >> x;
		if (q == 2) {
			cin >> y;
			xx.push_back(y);
		}
		in[i] = {q, x, y};
	}
	sort(xx.begin(), xx.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) A[i] = lower_bound(xx.begin(), xx.end(), A[i]) - xx.begin();
	for (int i = 0; i < M; ++i) {
		if (in[i].q == 1) in[i].x = lower_bound(xx.begin(), xx.end(), in[i].x) - xx.begin();
		else in[i].y = lower_bound(xx.begin(), xx.end(), in[i].y) - xx.begin();
	}
	for (int i = 0; i < N; ++i)
		if (A[i] < A[i + 1]) seg.update(A[i] + 1, A[i + 1], 1);
	for (int i = 0; i < M; ++i) {
		int q, x, y;
		q = in[i].q, x = in[i].x, y = in[i].y;
		if (q == 1) {
			printf("%d\n", seg.query(x));
		}
		else {
			if (A[x] < A[x + 1]) seg.update(A[x] + 1, A[x + 1], -1);
			if (A[x - 1] < A[x]) seg.update(A[x - 1] + 1, A[x], -1);
			if (y < A[x + 1]) seg.update(y + 1, A[x + 1], 1);
			if (A[x - 1] < y) seg.update(A[x - 1] + 1, y, 1);
			A[x] = y;
		}
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60