Submission #1200239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200239		crispxx	Sequence (APIO23_sequence)	C++20	0 / 100	438 ms	145484 KiB

sequence

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

#include "sequence.h"
// #include "grader.cpp"

using ordered_set = tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>;

struct MST {
	int n;
	vector<vector<int>> t;
	MST(vector<int> a) : n(a.size()), t(n << 2) {
		build(1, 1, n, a);
	}
	void build(int v, int l, int r, vector<int> &a) {
		if(l == r) {
			t[v] = {a[l - 1]};
			return;
		}
		int m = (l + r) >> 1;
		build(v << 1, l, m, a);
		build(v << 1 | 1, m + 1, r, a);
		merge(all(t[v << 1]), all(t[v << 1 | 1]), back_inserter(t[v]));
	}
	int get(int v, int l, int r, int ll, int rr, int x) {
		if(l > rr || r < ll) return 0;
		if(l >= ll && r <= rr) {
			return lower_bound(all(t[v]), x) - t[v].begin();
		}
		int m = (l + r) >> 1;
		return get(v << 1, l, m, ll, rr, x) + get(v << 1 | 1, m + 1, r, ll, rr, x);
	}
	int get(int l, int r, int x) {
		return get(1, 1, n, l, r, x);
	}
};

int sequence(int n, std::vector<int> a) {
	for(auto &x : a) x--;
	
	vector<vector<int>> idx(n);
	
	for(int i = 0; i < n; i++) {
		idx[a[i]].pb(i);
	}
	
	MST t(a);
	
	auto is_med = [&](int l, int r, int x, int freq) {
		int got = t.get(l + 1, r + 1, x);
		int l1 = got, r1 = got + freq - 1;
		int l2 = (l + r) >> 1, r2 = (l + r + 1) >> 1;
		// cout << nl;
		// cout << l << ' ' << r << nl;
		// cout << l1 << ' ' << r1 << nl;
		// cout << l2 << ' ' << r2 << nl;
		// cout << nl;
		return max(l1, l2) <= min(r1, r2);
	};
	
	// cout << is_med(0, 8, 0, 4) << nl;
	
	auto check = [&](int x) {
		for(int i = 0; i < n; i++) {
			if((int)idx[i].size() < x) continue;
			for(int j = 0; j + x - 1 < (int)idx[i].size(); j++) {
				if(is_med(idx[i][j], idx[i][j + x - 1], i, x)) {
					// cout << "Yes: " << x << ' ' << i + 1 << ' ' << j << nl;
					return true;
				}
			}
		}
		return false;
	};
	
	int l = 0, r = n;
	
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	
	return l;
	// return -1;
}

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