#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;
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);
}
}
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";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |