Submission #1271587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271587		bourbon	Alternating Heights (CCO22_day1problem1)	C++20	25 / 25	571 ms	4588 KiB

Main

#include<bits/stdc++.h>

using namespace std;


int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n,k,q;
	cin >> n >> k >> q;
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
		a[i]--;
	}




	vector<int> best(n);
	vector<vector<int>> adj(k);
	vector<int> vis(k);
	bool found = false;

	auto dfs = [&](auto && dfs, int u) -> bool {
		if(found) return found;
		vis[u] = 1;
		bool res = false;
		vector<int> p;
		for(auto v : adj[u]) {

			if(vis[v] == 1) {
				found = true;
				return true;
			}

			if(vis[v] == 2) continue;
			p.emplace_back(v);
		}

		for(int v : p) res |= (dfs(dfs,v));

		vis[u] = 2;

		return res;
	};

	auto check = [&](int l, int r) -> bool {

		found = false;
		if(l == r) return true;

		for(int i = 0; i < k; ++i) {
			adj[i].clear();
			vis[i] = 0;
		}

		int d = 0;
		for(int i = l; i < r; ++i) {
			if(d) {
				adj[a[i]].emplace_back(a[i + 1]);
			}
			else adj[a[i + 1]].emplace_back(a[i]);
			d ^= 1;
		}
		bool bad = false;
		for(int i = 0; i < k; ++i) {
			if(vis[i] == 0) bad |= dfs(dfs, i);
		}

		return !bad;
	};

	for(int i = 0; i < n; ++i) {
		int low = (i == 0 ? i : best[i - 1]), high = n - 1;
		while(low <= high) {
			int mid = (low + high) >> 1;
			if(check(i, mid)) {
				best[i] = mid;
				low = mid + 1;
			}
			else high = mid - 1;
		}

		//cout << "$ " << i << " " <<  best[i] << '\n';
	}

	for(int i = 0; i < q; ++i) {
		int l,r;
		cin >> l  >> r;
		--l;--r;
		if(best[l] >= r) {
			cout << "YES\n";
		}
		else cout << "NO\n";
	}


}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8