Submission #990873

#	Time	Username	Problem	Language	Result	Execution time	Memory
990873		Trisanu_Das	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	617 ms	20052 KiB

Main

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

int A[201010];
int last[201010];
vector<int> adj[201010];
int vis[201010];
bool dfs(int x) {
	if (vis[x]) return !~vis[x];
	vis[x] = -1;
	for (auto v : adj[x]) if (dfs(v)) return true;
	vis[x] = 1;
	return false;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	int Q;
	cin >> N >> K;
	cin >> Q;
	int i, j;
	for (i = 1; i <= N; i++) cin >> A[i];
	for (i = 1; i <= N; i++) {
		int l, r;
		l = i;
		r = N + 1;
		while (r - l > 1) {
			int m = l + r >> 1;
			for (j = 1; j <= K; j++) adj[j].clear(), vis[j] = 0;
			int c = 0;
			for (j = i + 1; j <= m; j++) {
				if (c) adj[A[j]].push_back(A[j - 1]);
				else adj[A[j - 1]].push_back(A[j]);
				c ^= 1;
			}
			c = 0;
			for (j = 1; j <= K; j++) if (!vis[j]) {
				if (dfs(j)) {
					c = 1;
					break;
				}
			}
			if (c) r = m;
			else l = m;
		}
		last[i] = l;
	}
	while (Q--) {
		int a, b;
		cin >> a >> b;
		if (last[a] < b) cout << "NO\n";
		else cout << "YES\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |    int m = l + r >> 1;
      |            ~~^~~

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