제출 #1259959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259959		proofy	선물 배송 (IZhO12_train)	C++20	0 / 100	0 ms	320 KiB

train

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> a(n);
	for (int& u : a) cin >> u, --u;

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

	vector<int> b = a;
	for (int& u : b) u = -u;

	vector<int> lis, pre(n, -1), dp(n);
	lis.reserve(n);
	for (int u : b) {
		int j = lower_bound(lis.begin(), lis.end(), u) - lis.begin();
		if (j == (int)lis.size()) lis.push_back(u);
		else lis[j] = u;

		dp[-u] = j + 1;
		if (j > 0) pre[-u] = -lis[j - 1];
	}

	int z = max_element(dp.begin(), dp.end()) - dp.begin();

	lis = vector<int>();
	lis.reserve(n);

	lis.push_back(z);
	while (pre[lis.back()] != -1) {
		lis.push_back(pre[lis.back()]);
	}

	reverse(lis.begin(), lis.end());

	vector<int> color(n);

	vector<int> next_g(n, n), prev_s(n, -1);
	vector<int> st;
	for (int i = 0; i < n; i++) {
		while (!st.empty() && a[st.back()] < a[i]) {
			next_g[st.back()] = i;
			st.pop_back();
		}
		st.push_back(i);
	}
	st = vector<int>();
	for (int i = n - 1; i >= 0; --i) {
		while (!st.empty() && a[st.back()] > a[i]) {
			prev_s[st.back()] = i;
			st.pop_back();
		}
		st.push_back(i);
	}
	

	for (int k = 0; k < (int)lis.size(); k++) {
		int u = lis[k];
		int j = where[u];
		color[j] = k + 1;

		while (prev_s[j] != -1) {
			j = prev_s[j];
			if (!color[j])
				color[j] = k + 1;
		}
		j = where[u];
		while (next_g[j] < n) {
			j = next_g[j];
			if (!color[j])
				color[j] = k + 1;
		}
	}

	for (int u : color) cout << u << " ";
	cout << "\n";
	for (int i = 0; i < n; i++) cout << color[where[i]] << " ";
	cout << "\n";
}

• Subtask 1: 0 / 100