This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 200010
#define LSB(A) (A&(-A))
#define LOG 20
int N,Q;
typedef std::pair<int,int> pii;
std::vector<pii> eventos;
std::vector<int> add[MAX];
std::vector<int> rem[MAX];
int ft[MAX];
typedef std::pair<int,int*> pipo;
int custos[101000];
int trava;
int armazena[MAX];
int valor[MAX];
int jump[MAX][LOG];
void gera_conexoes(){
std::deque<pii> st;
///Menor indice L em que o final esteja presente entre L e R
for(int i=MAX-1;i!=-1;--i){
///Adiciona o finalzinho
pii menor = {1e9+1,1e9+1};
for(auto&x:rem[i]){
pii conj = {eventos[x].first,x};
menor=std::min(menor,conj);
}
if(menor.first!=1e9+1){
while(st.size()&&st.front().first>=menor.first){
st.pop_front();
}
st.push_front(menor);
}
///Pega o valor
for(auto&x:add[i]){
int l=0,r=st.size()-1;
while(l<r){
int m = (l+r+1)/2;
if(eventos[st[m].second].second<=eventos[x].second){
l=m;
}else r=m-1;
}
jump[x][0]=st[l].second;
}
}
}
int jumps(int a,int b){
int pos = a;
for(int i=LOG-1;i!=-1;--i){
if(((1<<i)&b)&&jump[pos][i]!=-1){
pos=jump[pos][i];
}
}
return pos;
}
int tabp5[5005][5005];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>N>>Q;
for(int i=0;i!=N;++i){
int a,b;
std::cin>>a>>b;
eventos.push_back({a,b});
}
{
std::vector<pipo> comprime;
for(auto&x:eventos){
comprime.push_back({x.first,&x.first});
comprime.push_back({x.second,&x.second});
}
std::sort(comprime.begin(),comprime.end());
int last=-1,cord=1;
for(auto&x:comprime){
if(x.first!=last){
last=x.first;
++cord;
}
*x.second=cord;
}
trava=cord;
}
for(int i=0;i!=N;++i){
add[eventos[i].first].push_back(i);
rem[eventos[i].second].push_back(i);
}
gera_conexoes();
// for(int i=0;i!=N;++i)if(jump[i][0]==i)jump[i][0]=-1;
for(int j=1;j!=LOG;++j){
for(int i=0;i!=N;++i){
if(jump[i][j-1]==-1)jump[i][j]=-1;
else
jump[i][j]=jump[jump[i][j-1]][j-1];
}
}
for(int i=0;i!=Q;++i){
int s,t;
std::cin>>s>>t;
--s;--t;
if(s==t){
std::cout<<"0\n";
continue;
}
if(eventos[t].second<eventos[s].second){
std::cout<<"impossible\n";
continue;
}
int cord = eventos[s].second;
int l=0,r=1e9;
while(l<r){
int m = (l+r)/2;
int q=jumps(t,m);
if(eventos[q].first<=cord){
r=m;
}else l=m+1;
}
// std::cout<<"ve "<<l<<"\n";
int q=jumps(t,l);
if(q!=s){
++l;
}
// std::cout<<"Val R: "<<r<<"\n";
if(r==1e9){
std::cout<<"impossible\n";
continue;
}
std::cout<<l<<"\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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |