Submission #698401

#	Time	Username	Problem	Language	Result	Execution time	Memory
698401		emptypringlescan	Alternating Heights (CCO22_day1problem1)	C++14	10 / 25	1035 ms	4408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
vector<int> adj[3005];
bool cyc=false;
bitset<3005> v,isdoing;
void dfs(int x){
	v[x]=1;
	isdoing[x]=1;
	for(int i:adj[x]){
		if(isdoing[i]) cyc=true;
		else if(!v[i]) 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;
			bool ev=0;
			for(int j=0; j<=k; j++){
				adj[j].clear();
			}
			v.reset();
			for(int j=i+1; j<=mid; j++){
				if(ev){
					adj[arr[j]].push_back(arr[j-1]);
				}
				else{
					adj[arr[j-1]].push_back(arr[j]);
				}
				ev^=1;
			}
			cyc=false;
			for(int j=i; j<=mid; j++){
				if(!v[arr[j]]) dfs(arr[j]);
			}
			//cout << i << ' ' << mid << ' ' << cyc << ' ' << found << '\n';
			if(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: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8