제출 #698379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
698379		emptypringlescan	Alternating Heights (CCO22_day1problem1)	C++17	4 / 25	813 ms	11056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[3005];
bool cyc=false,v[3005],isdoing[3005];
void dfs(int x){
	if(isdoing[x]) cyc=true;
	if(v[x]) return;
	v[x]=1;
	
	isdoing[x]=1;
	for(int i:adj[x]) dfs(i);
	isdoing[x]=0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k,q;
	cin >> n >> k >> q;
	int arr[n];
	for(int i=0; i<n; i++) cin >> arr[i];
	int prec[n];
	for(int i=0; i<n; i++){
		int lo=i,hi=n-1,mid;
		while(lo<hi){
			mid=(lo+hi+1)/2;
			int ev=0;
			int in[n];
			for(int j=0; j<n; j++){
				adj[j].clear();
				v[j]=0;
				in[j]=0;
			}
			for(int j=i+1; j<=mid; j++){
				if(ev){
					adj[arr[j]].push_back(arr[j-1]);
					in[arr[j-1]]++;
				}
				else{
					adj[arr[j-1]].push_back(arr[j]);
					in[arr[j]]++;
				}
				ev^=1;
			}
			bool found=true;
			cyc=false;
			for(int j=i; j<=mid; j++){
				if(!in[arr[j]]){
					dfs(arr[j]);
					
				}
			}
			for(int j=i; j<=mid; j++) if(!v[arr[j]]) found=false;
			//cout << i << ' ' << mid << ' ' << cyc << ' ' << found << '\n';
			if(!found||cyc){
				hi=mid-1;
			}
			else lo=mid;
		}
		prec[i]=lo;
		//cout << lo << ' ';
	}
	for(int i=0; i<q; i++){
		int a,b;
		cin >> a >> b;
		a--; b--;
		if(b<=prec[a]) cout << "YES\n";
		else cout << "NO\n";
	}
}

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