Submission #694863

#	Time	Username	Problem	Language	Result	Execution time	Memory
694863		US3RN4M3	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	526 ms	13840 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;
		scanf("%d %d\n", &x, &y);
		if(bes[x - 1] >= y - 1) printf("YES\n");
		else printf("NO\n");
	}
}

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d %d\n", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

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