Submission #1200473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200473		_rain_	Alternating Heights (CCO22_day1problem1)	C++20	25 / 25	769 ms	4560 KiB

Main

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

const int N=(int)3000;
vector<int>ke[N+2];
int vis[N+2]={};
int n,k,q;
int a[N+2]={},ans[N+2]={};
	
	void add_canh(int u,int v){
		ke[u].push_back(v);
	}
	
	void reset(){
		for(int i=1;i<=k;++i) ke[i].clear();
		for(int i=1;i<=k;++i) vis[i]=0;
		return;
	}
	
	bool dfs(int u){
		vis[u]=1;
		for(auto&v:ke[u]){
			if (vis[v]==0) {
				if (dfs(v)) return true;
			}
			else if (vis[v]==1) return true;
		}
		vis[u]=2;
		return false;
	}
	
	bool possible(int l,int r){
		if (l==r) return true;
		reset();
		int turn = 0;
		for(int i=l;i<r;++i){
			if (turn==0) add_canh(a[i],a[i+1]);
				else add_canh(a[i+1],a[i]);
			turn=!turn;
		}
		
		for(int i=1;i<=k;++i) {
			if (vis[i]==0 && dfs(i)) return false;
		}
		return true;
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
//	freopen("main.inp","r",stdin);
	
	cin>>n>>k>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i){
		int low=i,high=n;
		while (low<=high){
			int mid=(low+high)/2;
			if (possible(i,mid)){
				ans[i]=mid;
				low=mid+1;
			}
			else high=mid-1;
		}
	}
	while(q--){
		int l,r; cin>>l>>r;
		if (ans[l]>=r){
			cout<<"YES\n";
		}
		else cout<<"NO\n";
	}
}

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