Submission #699028

#	Time	Username	Problem	Language	Result	Execution time	Memory
699028		gghx	Alternating Heights (CCO22_day1problem1)	C++14	25 / 25	582 ms	13980 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++) rightmost[i]=i;
	ll right=0;
	for(int i=0;i<n;i++){
		//check range (i,right+1)
		while(true){
			rightmost[i]=right;
			if(right>n-1) break;
			right++;
			vector<ll> adj[k],adj1[k];
			bool bigger=true;
			bool die=false;
			for(int j=i;j<right-1;j++){
				if(arr[j]==arr[j+1]){
					die=true;
				}
				if(bigger) adj[arr[j]].push_back(arr[j+1]);
				else adj[arr[j+1]].push_back(arr[j]);
				if(bigger) adj1[arr[j+1]].push_back(arr[j]);
				else adj1[arr[j]].push_back(arr[j+1]);
				bigger=1-bigger;
			}
			if(die==true){
				right--;
				break;
			}
			ll indeg[k];
			for(int j=0;j<k;j++) indeg[j]=adj[j].size();
			queue<ll> q;
			ll count=0;
			for(int j=0;j<k;j++){
				if(indeg[j]==0){
					q.push(j);
					count++;
				}
			}
			while(!q.empty()){
				ll tp=q.front(); q.pop();
				for(int j=0;j<adj1[tp].size();j++){
					ll neighbour=adj1[tp][j];
					if(indeg[neighbour]==0) continue;
					if(indeg[neighbour]==1){
						indeg[neighbour]=0;
						q.push(neighbour);
						count++;
					}
					else indeg[neighbour]--;
				}
			}
			if(count<k){
				right--;
				break;
			}
		}	
		rightmost[i]--;
	}
	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:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int j=0;j<adj1[tp].size();j++){
      |                 ~^~~~~~~~~~~~~~~~

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