Submission #1272418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272418		thuhienne	Alternating Heights (CCO22_day1problem1)	C++20	0 / 25	1096 ms	3364 KiB

Main

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

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

int adj[3009][3009];
//co canh tu i -> j khi va chi khi ai > aj

bool circuit;

int visited[3009];
void findcircuit(int node) {
	visited[node] = 1;
	for (int nex = 1;nex <= n;nex++) if (adj[node][nex] && 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) adj[arr[i]][arr[i + 1]]++;
		else adj[arr[i + 1]][arr[i]]++;
		while (checkcircuit()) {
			if ((pt - 1) % 2 != 0) adj[arr[pt - 1]][arr[pt]]--;
			else adj[arr[pt]][arr[pt - 1]]--;
			pt--;
		}
		if (i % 2 != 0) maxr[i] = pt;
	}
	//reset
	for (int i = 1;i <= k;i++) for (int j = 1;j <= k;j++) adj[i][j] = 0;
	pt = n;
	//even indices
	maxr[n] = n;
	for (int i = n - 1;i >= 1;i--) {
		if (i % 2 == 0) adj[arr[i]][arr[i + 1]]++;
		else adj[arr[i + 1]][arr[i]]++;
		while (checkcircuit()) {
			if ((pt - 1) % 2 == 0) adj[arr[pt - 1]][arr[pt]]--;
			else adj[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: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8