Submission #698996

#	Time	Username	Problem	Language	Result	Execution time	Memory
698996		gghx	Alternating Heights (CCO22_day1problem1)	C++14	0 / 25	1097 ms	569008 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n,k,qn;
	cin>>n>>k>>qn;
	ll arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
		arr[i]--;	
	}
	ll rightmost[n]; //the rightmost workable n
	for(int i=0;i<n;i++){
		int low=i+1,high=n-1,ans=i;
		while(low<=high){
			int mid=(low+high)/2;
			vector<ll> adj[k];
			bool more=1;
			for(int j=i;j<=mid-1;j++){
				if(more==1) adj[arr[j]].push_back(arr[j+1]);
				else adj[arr[j+1]].push_back(arr[j]);
				more=1-more;
			}
			//detect cycle in adj
			bool cycle=0;
			for(int l=0;l<k;l++){
				if(cycle==1) break;
				bool visited[k];
				fill(visited,visited+k,0);
				visited[l]=1;
				queue<ll> q;
				q.push(l);
				while(!q.empty()){
					if(cycle==1) break;
					ll tp=q.front();
					q.pop();
					for(int a=0;a<adj[tp].size();a++){
						if(adj[tp][a]==l){
							cycle=1; break;
						}
						else visited[adj[tp][a]]=1;
						q.push(adj[tp][a]);
					}
				}
				
			}
			if(cycle==0){
				ans=mid;
				low=mid+1;
			}
			else high=mid-1;
		}
		rightmost[i]=ans;
	}
	for(int i=0;i<qn;i++){
		ll x,y; cin>>x>>y;
		x--; y--;
		if(y<=rightmost[x]) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |      for(int a=0;a<adj[tp].size();a++){
      |                  ~^~~~~~~~~~~~~~~

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