# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1149046 | emptypringlescan | popa (BOI18_popa) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int *l, int *r){
vector<int> adj[n];
int lft[n],rgt[n];
for(int i=0; i<n; i++){
lft[i]=rgt[i]=-1;
}
stack<int> st;
st.push(0);
for(int i=1; i<n; i++){
int prev=-1;
while(!st.empty()){
int x=query(st.top(),i,i,i);
if(x==0){
break;
}
prev=st.top();
st.pop();
}
if(!st.empty()){
adj[st.top()].pop_back();
adj[st.top()].push_back(i);
}
if(prev!=-1) adj[i].push_back(prev);
st.push(i);
}
for(int i=0; i<n; i++){
for(int j:adj[i]){
if(j<i) lft[i]=j;
else rgt[i]=j;
}
}
l=lft; r=rgt;
while((int)st.size()>1) st.pop();
return st.top();
}