제출 #698392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698392		penguin133	Alternating Heights (CCO22_day1problem1)	C++17	10 / 25	1082 ms	4608 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<=k;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<=k;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();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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