Submission #698390

#	Time	Username	Problem	Language	Result	Execution time	Memory
698390		penguin133	Alternating Heights (CCO22_day1problem1)	C++17	6 / 25	1071 ms	4684 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], rgt[3005];
int vis[3005], vis2[3005], cyc = 0;
vector <int> 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 : v[x])dfs(i);
	vis2[x] = 0;
}
void solve(){
	cin >> n >> k >> q;
	for(int i=1;i<=n;i++)cin >> A[i];
	for(int i=1;i<=n;i++){
		int lo = i + 1, hi = n, ans = i;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			for(int j=1;j<=k;j++)v[j].clear(), vis[j] = 0;
			for(int j=i+1;j<=mid;j++){
				if((j - i)%2)v[A[j-1]].push_back(A[j]);
				else v[A[j]].push_back(A[j-1]);
			}
			cyc = 0;
			for(int j=1;j<=n;j++)if(!vis[j])dfs(j);
			if(cyc)hi = mid - 1;
			else ans = mid, lo = mid + 1;
		}
		rgt[i] = max(rgt[i], ans);
	}
	for(int i=1;i<=n;i++){
		int lo = i + 1, hi = n, ans = i;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			for(int j=1;j<=k;j++)v[j].clear(), vis[j] = 0;
			for(int j=i+1;j<=mid;j++){
				if((j - i)%2 == 0)v[A[j-1]].push_back(A[j]);
				else v[A[j]].push_back(A[j-1]);
			}
			cyc = 0;
			for(int j=1;j<=n;j++)if(!vis[j])dfs(j);
			if(cyc)hi = mid - 1;
			else ans = mid, lo = mid + 1;
		}
		rgt[i] = max(rgt[i], ans);
	}
	while(q--){
		int l, r; cin >> l >> r;
		cout << (rgt[l] >= r ? "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:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

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