Submission #1167052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167052		WH8	Alternating Heights (CCO22_day1problem1)	C++20	0 / 25	1002 ms	3836 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define mp make_pair
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
struct SparseTable{
	vector<vector<int>> st;
	int n, max_log;
	int log2_floor(unsigned long long i) {
		return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
	}
	void initialize(const vector<int>& v) {
        n = v.size();
        max_log = log2_floor(n) + 1;
        st.assign(max_log, vector<int>(n));

        // Initialize the first row of the sparse table
        for (int i = 0; i < n; i++) {
            st[0][i] = v[i];
        }

        // Fill the sparse table
        for (int i = 1; i < max_log; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
	int query(int a, int b) {
        int i = log2_floor(b - a + 1);
        return min(st[i][a], st[i][b - (1 << i) + 1]);
    }
};


vector<pair<int,int>> cy;
int n,k,q;
int a[3005];
vector<vector<pll>> al(3005);
vector<pll> ps;
int col[3005];

void dfs(int x){
	for(auto [it, ind] :al[x]){
		if(col[it]==2)continue;
		if(col[it]==1){
			bool found=false;
			int mn=ind, mx=ind;
			//~ printf("cycle towards %lld, edge ind %lld\n",it,ind);
			for(int j=ps.size()-1; j>=0;j--){
				if(ps[j].f==it){
					found=true;
					break;
				}
				mn=min(mn,ps[j].s);
				mx=max(mx,ps[j].s);
			}
			assert(found);
			cy.pb({mn, mx});
		}
		if(col[it]==0){
			col[it]=1;
			ps.pb({it, ind});
			dfs(it);
		}
	}
	ps.pop_back();
	col[x]=2;
}

signed main(){
	cin>>n>>k>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i>=1){
			if(i%2==1)al[a[i-1]].pb({a[i], i+1});
			else al[a[i]].pb({a[i-1], i+1});
		}
	}
	col[1]=1;
	for(int i=1;i<=k;i++){
		if(col[i]==2)continue;
		col[i]=1;
		ps.clear();
		ps.pb({i, -1});
		dfs(i);
	}
	//~ for(auto it:cy){
		//~ cout<<it.f<<" "<<it.s<<"|";
	//~ }
	sort(cy.begin(),cy.end());
	vector<int> stv;
	for(auto it:cy){
		stv.pb(it.s);
	}
	SparseTable st;
	st.initialize(stv);
	
	for(int i=0;i<q;i++){
		int l,r;cin>>l>>r;
		l++;
		int lb=lower_bound(cy.begin(),cy.end(),mp(l,(int)-1))-cy.begin();
		int rb=upper_bound(cy.begin(),cy.end(),mp(r,(int)1e15))-cy.begin()-1;
		if(rb<lb){
			cout<<"YES\n";
			continue;
		}
		int mn=st.query(lb, rb);
		if(mn<=r)cout<<"NO\n";
		else cout<<"YES\n";
	}
}

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