Submission #698406

#	Time	Username	Problem	Language	Result	Execution time	Memory
698406		emptypringlescan	Alternating Heights (CCO22_day1problem1)	C++14	25 / 25	916 ms	4552 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,v[3005],isdoing[3005];
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;
}
void fastscan(int &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    register int c;
  
    number = 0;
  
    // extract current character from buffer
    c = getchar();
    if (c=='-')
    {
        // number is negative
        negative = true;
  
        // extract the next character from the buffer
        c = getchar();
    }
  
    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
  
    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k,q;
	fastscan(n); fastscan(k); fastscan(q);
	int arr[n];
	for(int i=0; i<n; i++) fastscan(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;
			for(int j=0; j<=k; j++){
				adj[j].clear();
				v[j]=0;
				isdoing[j]=0;
			}
			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;
		fastscan(a); fastscan(b);
		a--; b--;
		if(b<=prec[a]) cout << "YES\n";
		else cout << "NO\n";
	}
}

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