Submission #1272422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272422		thuhienne	Alternating Heights (CCO22_day1problem1)	C++20	25 / 25	169 ms	4560 KiB

Main

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

int n,k,q;
int arr[3009];
int maxr[3009];

vector <int> adj[3009];
//co canh tu i -> j khi va chi khi ai > aj
void addedge(int u,int v) {
	adj[u].push_back(v);
}
void remedge(int u,int v) {
	for (int i = 0;i < adj[u].size();i++) {
		if (adj[u][i] == v) {
			adj[u].erase(adj[u].begin() + i);
			return;
		}
	}
}

bool circuit;

int visited[3009];
void findcircuit(int node) {
	visited[node] = 1;
	for (auto nex : adj[node]) if (visited[nex] != 2) {
		if (visited[nex] == 1) {
			circuit = 1;
			return;
		}
		findcircuit(nex);
		if (circuit) return;
	}
	visited[node] = 2;
}
bool checkcircuit() {
	for (int i = 1;i <= n;i++) visited[i] = 0;
	circuit = 0;
	for (int i = 1;i <= n;i++) if (!visited[i]) {
		findcircuit(i);
		if (circuit) return 1;
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	//freopen(".inp","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> k >> q;
	for (int i = 1;i <= n;i++) cin >> arr[i];
	maxr[n] = n;
	//odd indices
	int pt = n;
	for (int i = n - 1;i >= 1;i--) {
		if (i % 2 != 0) addedge(arr[i],arr[i + 1]);
		else addedge(arr[i + 1],arr[i]);
		while (checkcircuit()) {
			if ((pt - 1) % 2 != 0) remedge(arr[pt - 1],arr[pt]);
			else remedge(arr[pt],arr[pt - 1]);
			pt--;
		}
		if (i % 2 != 0) maxr[i] = pt;
	}
	//reset
	for (int i = 1;i <= k;i++) adj[i].clear();
	pt = n;
	//even indices
	maxr[n] = n;
	for (int i = n - 1;i >= 1;i--) {
		if (i % 2 == 0) addedge(arr[i],arr[i + 1]);
		else addedge(arr[i + 1],arr[i]);
		while (checkcircuit()) {
			if ((pt - 1) % 2 == 0) remedge(arr[pt - 1],arr[pt]);
			else remedge(arr[pt],arr[pt - 1]);
			pt--;
		}
		if (i % 2 == 0) maxr[i] = pt;
	}
	while (q--) {
		int l,r;cin >> l >> r;
		cout << (maxr[l] >= r ? "YES" : "NO") << '\n';
	}
}

/*
  Nho doi vai em gay
			  co gai ay ngoi duoi goc pho nen tho ...
*/

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