Submission #698397

#	Time	Username	Problem	Language	Result	Execution time	Memory
698397		penguin133	Alternating Heights (CCO22_day1problem1)	C++17	25 / 25	416 ms	13900 KiB

Main

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

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, k, q;
int A[3005], lft[3005];
int vis[3005], vis2[3005], cyc = 0, lp = 0;
vector <pi> v[3005];
void dfs(int x){
	if(vis2[x]){
		cyc = 1;
		return;
	}
	else if(vis[x])return;
	vis[x] = vis2[x] = 1;
	for(auto [i, j] : v[x])if(j > lp)dfs(i);
	vis2[x] = 0;
}

bool hello(){
	for(int i=1;i<=k;i++)vis[i] = 0;
	cyc=  0;
	for(int i=1;i<=k;i++)if(!vis[i])dfs(i);
	return cyc;
}
void solve(){
	cin >> n >> k >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	lft[1] = 1;
	lp = 1;
	for(int i=2;i<=n;i++){
		lft[i] = i;
		if(i%2 == 0)v[A[i-1]].push_back({A[i], i});
		else v[A[i]].push_back({A[i-1], i});
		while(hello())lp++;
		lft[i] = min(lft[i], lp);
	}
	lp = 1;
	for(int i=1;i<=k;i++)v[i].clear();
	for(int i=2;i<=n;i++){
		if(i%2)v[A[i-1]].push_back({A[i], i});
		else v[A[i]].push_back({A[i-1], i});
		while(hello())lp++;
		lft[i] = min(lft[i], lp);
	}
	while(q--){
		int l, r; cin >> l >> r;
		cout << (lft[r] <= l ? "YES\n" : "NO\n");
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

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

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