# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
698996 | gghx | Alternating Heights (CCO22_day1problem1) | C++14 | 1097 ms | 569008 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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++){
int low=i+1,high=n-1,ans=i;
while(low<=high){
int mid=(low+high)/2;
vector<ll> adj[k];
bool more=1;
for(int j=i;j<=mid-1;j++){
if(more==1) adj[arr[j]].push_back(arr[j+1]);
else adj[arr[j+1]].push_back(arr[j]);
more=1-more;
}
//detect cycle in adj
bool cycle=0;
for(int l=0;l<k;l++){
if(cycle==1) break;
bool visited[k];
fill(visited,visited+k,0);
visited[l]=1;
queue<ll> q;
q.push(l);
while(!q.empty()){
if(cycle==1) break;
ll tp=q.front();
q.pop();
for(int a=0;a<adj[tp].size();a++){
if(adj[tp][a]==l){
cycle=1; break;
}
else visited[adj[tp][a]]=1;
q.push(adj[tp][a]);
}
}
}
if(cycle==0){
ans=mid;
low=mid+1;
}
else high=mid-1;
}
rightmost[i]=ans;
}
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";
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |