Submission #982557

#	Time	Username	Problem	Language	Result	Execution time	Memory
982557		TranGiaHuy1508	Sequence (APIO23_sequence)	C++17	100 / 100	1359 ms	66380 KiB

sequence

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

const int inf = 1e9;
using ii = pair<int, int>;

template <class T, T (*merge)(T, T), T def = T()>
struct Segtree {
	vector<T> tree, lazy;
	int _n;

	Segtree() {}
	Segtree(int N){
		setup(N);
	}

	void setup(int N){
		tree.assign(4 * N, T());
		lazy.assign(4 * N, T());
		_n = N;
	}

	void apply(int i, T delta){
		tree[i] += delta;
		lazy[i] += delta;
	}

	void push(int i){
		if (lazy[i] == T()) return;
		apply(i<<1, lazy[i]);
		apply(i<<1|1, lazy[i]);
		lazy[i] = T();
	}

	void update(int tl, int tr, T delta){
		update(1, 0, _n - 1, tl, tr, delta);
	}

	void update(int i, int l, int r, int tl, int tr, T delta){
		if (tl <= l && r <= tr){
			apply(i, delta);
			return;
		}
		if (tl > r || tr < l) return;

		push(i);
		int mid = (l + r) >> 1;

		update(i<<1, l, mid, tl, tr, delta);
		update(i<<1|1, mid+1, r, tl, tr, delta);
		tree[i] = merge(tree[i<<1], tree[i<<1|1]);
	}

	T get(int tl, int tr){
		return get(1, 0, _n - 1, tl, tr);
	}

	T get(int i, int l, int r, int tl, int tr){
		if (tl <= l && r <= tr) return tree[i];
		if (tl > r || tr < l) return def;

		push(i);
		int mid = (l + r) >> 1;

		T resl = get(i<<1, l, mid, tl, tr);
		T resr = get(i<<1|1, mid+1, r, tl, tr);
		return merge(resl, resr);
	}
};

template <class T = int>
T fmin(T a, T b) { return min(a, b); }

template <class T = int>
T fmax(T a, T b) { return max(a, b); }

Segtree<int, fmin, inf> stmin;
Segtree<int, fmax, -inf> stmax;

int sequence(int N, vector<int> A){
	vector<vector<int>> locations(N + 1);
	for (int i = 0; i < N; i++) locations[A[i]].push_back(i + 1);

	stmin.setup(N + 1);
	stmax.setup(N + 1);

	for (int i = 1; i <= N; i++) stmin.update(i, N, 1);
	for (int i = 1; i <= N; i++) stmax.update(i, N, 1);

	auto is_intersect = [&](ii p1, ii p2){
		if (p1.first > p2.first) swap(p1, p2);
		return p1.second >= p2.first;
	};

	int ans = 0;
	for (int num = 1; num <= N; num++){
		if (locations[num].empty()) continue;
		for (auto j: locations[num]) stmin.update(j, N, -2);
		for (auto j: locations[num]) stmax.update(j, N, -2);

		for (int idxl = (int)locations[num].size() - 1; idxl >= 0; idxl--){
			int l = locations[num][idxl];

			stmin.update(l, N, 2);
			stmax.update(l, N, 2);

			for (int idxr = idxl + ans; idxr < (int)locations[num].size(); idxr++){
				int r = locations[num][idxr];

				ii range_lhs = {stmin.get(0, l - 1), stmax.get(0, l - 1)};
				ii range_rhs = {stmin.get(r, N) - 2 * (ans + 1), stmax.get(r, N)};

				if (is_intersect(range_lhs, range_rhs)){
					ans++;
				}
				else break;
			}
		}

		for (auto j: locations[num]) stmin.update(j, N, -2);
		for (auto j: locations[num]) stmax.update(j, N, -2);
	}

	return ans;
}

#ifdef LOCAL

int main(){
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];

	cout << "Answer: " << sequence(n, a) << "\n";
}

#endif // LOCAL

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18