Frontier

input/code.cpp: In function 'int main()':
input/code.cpp:83:29: warning: unused variable 'sl' [-Wunused-variable]
   83 |                         int sl = l;
      |                             ^~
input/code.cpp:87:29: warning: unused variable 'er' [-Wunused-variable]
   87 |                         int er = r;
      |                             ^~

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

void fail() {
	cout << "NO" << endl;
	exit(0);
}

using vi = vector<int>;

#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = a; i < (b); ++i)

vi topoSort(const vector<vi>& gr) {
	vi indeg(sz(gr)), ret;
	for (auto& li : gr) for (int x : li) indeg[x]++;
	queue<int> q;
	rep(i, 0, sz(gr)) if (indeg[i] == 0) q.push(i);
	while (!q.empty()) {
		int i = q.front();
		ret.push_back(i);
		q.pop();
		for (int x : gr[i])
			if (--indeg[x] == 0) q.push(x);
	}
	if (sz(ret) < sz(gr)) return {};
	return ret;
}

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

	int n, s;
	cin >> n >> s;

	s++;
	vector<vector<int>> occ(s);

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

		occ[v[i]].push_back(i);
	}

	vector<vector<int>> g(s);

	for (int i = 0; i < s; ++i) {
		if (!occ[i].size()) continue;
		for (int j = i + 1; j < s; ++j) {
			if (!occ[j].size()) continue;

			int min_i = occ[i].front();
			int max_i = occ[i].back();
			int min_j = occ[j].front();
			int max_j = occ[j].back();

			if (max_i < min_j) continue;
			if (max_j < min_i) continue;

			int l = max(min_i, min_j);
			int r = min(max_i, max_j);

			if (r < l) {
				continue;
			}

			{
				auto it = lower_bound(all(occ[i]), l);
				if (it == end(occ[i]) || *it > r) continue;
			}
			{
				auto it = lower_bound(all(occ[j]), l);
				if (it == end(occ[j]) || *it > r) continue;
			}

			if (v[l] == v[r]) {
				fail();
			}

			int sl = l;
			int el = *prev(upper_bound(all(occ[v[l]]), r));

			int sr = *lower_bound(all(occ[v[r]]), l);
			int er = r;

			if (el > sr) {
				fail();
			}

			g[v[l]].push_back(v[l] == i ? j : i);
		}
	}

	auto t = topoSort(g);

	if (!t.size()) fail();
	cout << "YES" << endl;
	
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED