Submission #1182486

#TimeUsernameProblemLanguageResultExecution timeMemory
1182486UmairAhmadMirzaAlternating Heights (CCO22_day1problem1)C++20
4 / 25
987 ms4440 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int const N=3005; int const mod=1e9+7; int n,k,q; int seq[N]; int MX[N]; int MX2[N]; vector<int> adj[N]; int tar=0; bool killed=0; bool seen[N]; void dfs(int node){ if(seen[node] || killed || node==tar){ killed=1; return; } seen[node]=1; for(int i:adj[node]) dfs(i); } bool con(int a,int b){ killed=0; tar=b; for (int i = 0; i <=k; ++i) seen[i]=0; // cerr<<a<<endl; dfs(a); return killed; } int main(){ cin>>n>>k>>q; for (int i = 1; i <=n; ++i) cin>>seq[i]; for(int s=1;s<=n;s++){ bool bb=0; MX[s]=n; for(int i=0;i<=k;i++) adj[i].clear(); for(int i=s+1;i<=n;i++){ if(bb==0){ if(con(seq[i],seq[i-1])){ MX[s]=i-1; break; } adj[seq[i-1]].push_back(seq[i]); } else{ if(con(seq[i-1],seq[i])){ MX[s]=i-1; break; } adj[seq[i]].push_back(seq[i-1]); } bb^=1; } } for(int s=1;s<=n;s++){ bool bb=1; MX2[s]=n; for(int i=0;i<=k;i++) adj[i].clear(); for(int i=s+1;i<=n;i++){ if(bb==0){ if(con(seq[i],seq[i-1])){ MX2[s]=i-1; break; } adj[seq[i-1]].push_back(seq[i]); } else{ if(con(seq[i-1],seq[i])){ MX2[s]=i-1; break; } adj[seq[i]].push_back(seq[i-1]); } bb^=1; } } while(q--){ int a,b; cin>>a>>b; if(max(MX[a],MX2[a])<b) cout<<"NO"<<'\n'; else cout<<"YES"<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...