Submission #694861

#	Time	Username	Problem	Language	Result	Execution time	Memory
694861		US3RN4M3	Alternating Heights (CCO22_day1problem1)	C++17	7 / 25	1093 ms	2436 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 3005;
vector<pair<int, int>> graph[mx];
int nums[mx];
int bes[mx];
char vis[mx];
int l, r, n, k, q;
bool cond;
void dfs(int cur) {
	vis[cur] = 1;
	for(auto [nxt, pos] : graph[cur]) if(l <= pos && pos < r) {
		if(vis[nxt] == 1) {
			cond = true;
			return;
		}
		if(!vis[nxt]) dfs(nxt);
		if(cond) return;
	}
	vis[cur] = 2;
}
void test() {
	r = l;
	for(int delta = 2048; delta >= 1; delta >>= 1) {
		r += delta;
		if(r >= n) {
			r -= delta;
			continue;
		}
		cond = false;
		memset(vis, 0, sizeof(vis));
		for(int i = l; i <= r; i++) {
			if(vis[nums[i]] == 0) dfs(nums[i]);
		}
		if(cond) r -= delta;
	}
	bes[l] = r;
}
main() {
	cin >> n >> k >> q;
	for(int i = 0; i < n; i++) cin >> nums[i];
	for(int i = 1; i < n; i++) {
		if(i & 1) {
			graph[nums[i]].push_back({nums[i - 1], i - 1});
		} else {
			graph[nums[i - 1]].push_back({nums[i], i - 1});
		}
	}
	for(l = 0; l < n; l++) {
		test();
	}
	for(int i = 0; i < q; i++) {
		int x, y; cin >> x >> y;
		if(bes[x - 1] >= y - 1) cout << "YES" << "\n";
		else cout << "NO" << "\n";
	}
}

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~

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