Submission #742917

#	Time	Username	Problem	Language	Result	Execution time	Memory
742917		flappybird	Employment (JOI16_employment)	C++17	100 / 100	206 ms	13136 KiB

employment

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int T[MAX];
int B[MAX];
int C[MAX];
int D[MAX];
struct fenwick {
	int N;
	vector<int> tree;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, int x) {
		i = N - i + 1;
		while (i <= N) {
			tree[i] += x;
			i += i & -i;
		}
	}
	int sum(int i) {
		int ans = 0;
		i = N + 1 - i;
		while (i) {
			ans += tree[i];
			i -= i & -i;
		}
		return ans;
	}
};
fenwick fen;
int cnt[MAX];
void refresh(int x) {
	int l, r;
	l = A[x - 1] < A[x];
	r = A[x] >= A[x + 1];
	cnt[x] = 0;
	if (l && r) cnt[x] = 1;
	if (!l && !r) cnt[x] = -1;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int i;
	vector<int> v;
	for (i = 1; i <= N; i++) cin >> A[i], v.push_back(A[i]);
	for (i = 1; i <= Q; i++) {
		cin >> T[i];
		if (T[i] == 1) cin >> B[i];
		else cin >> C[i] >> D[i], v.push_back(D[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for (i = 1; i <= N; i++) A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin() + 1;
	for (i = 1; i <= Q; i++) if (T[i] == 2) D[i] = lower_bound(v.begin(), v.end(), D[i]) - v.begin() + 1;
	int K = v.size();
	fen = fenwick(K);
	for (i = 1; i <= N; i++) refresh(i), fen.upd(A[i], cnt[i]);
	for (i = 1; i <= Q; i++) {
		if (T[i] == 1) {
			int ind = lower_bound(v.begin(), v.end(), B[i]) - v.begin() + 1;
			if (ind > K) cout << 0 << ln;
			else cout << fen.sum(ind) << ln;
		}
		else {
			for (int x = C[i] - 1; x <= C[i] + 1; x++) fen.upd(A[x], -cnt[x]);
			A[C[i]] = D[i];
			for (int x = C[i] - 1; x <= C[i] + 1; x++) {
				refresh(x);
				fen.upd(A[x], cnt[x]);
			}
		}
	}
}

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