Submission #743579

#	Time	Username	Problem	Language	Result	Execution time	Memory
743579		flappybird	Alternating Heights (CCO22_day1problem1)	C++17	10 / 25	1070 ms	18496 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int last[MAX];
vector<int> adj[MAX];
int vis[MAX];
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" << ln;
		else cout << "YES" << ln;
	}
}

Compilation message (stderr)

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

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