Submission #1259957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259957		proofy	New Year Train (IZhO12_train)	C++20	0 / 100	1 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);
	
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);

	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";
}

Compilation message (stderr)

train.cpp: In function 'int main()':
train.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen("a.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
train.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen("a.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100