제출 #1200321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200321		crispxx	서열 (APIO23_sequence)	C++20	0 / 100	2098 ms	145460 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"

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 = l + got, r1 = l + 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 < (int)idx[i].size(); j++) {
				for(int k = j; k < (int)idx[i].size(); k++) {
					if(k - j + 1 < x) continue;
					if(is_med(idx[i][j], idx[i][k], i, k - j + 1)) {
						// cout << "Yes: " << x << ' ' << i + 1 << ' ' << j << nl;
						return true;
					}
				}
			}
		}
		return false;
	};
	
	int l = 0, r = 1e9;
	
	while(l < r) {
		int mid = (l + r + 1) >> 1;
		
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	
	assert(l >= 1 && l <= n);
	
	return l;
}

• 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