제출 #1271583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271583		bourbon	Alternating Heights (CCO22_day1problem1)	C++20	10 / 25	1096 ms	4460 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<set<int>> adj(k);
	vector<int> vis(k);

	auto dfs = [&](auto && dfs, int u) -> bool {
		vis[u] = 1;
		bool res = false;
		for(auto v : adj[u]) {
			if(vis[v] == 1) {
				return true;
			}
			if(vis[v] == 2) continue;
			res |= dfs(dfs, v);
		}

		vis[u] = 2;

		return res;
	};

	auto check = [&](int l, int r) -> bool {
		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]].insert(a[i + 1]);
			}
			else adj[a[i + 1]].insert(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, 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: 0 / 7
• Subtask 4: 0 / 8