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>
using namespace std;
typedef long long ll;
const int MX=2e5+5;
int N,Q;
int L[MX], R[MX];
int up[MX][20];
map<int,int> id;
vector<pair<int,int>> open[MX], cl[MX];
struct segtree {
pair<int,int> t[4*MX];
set<pair<int,int>> S[MX];
void upd(int v, int l, int r, int pos) {
if(pos<l || r<pos) return;
if(l==r) {
t[v]=*S[l].begin();
return;
}
int m=(l+r)/2;
upd(v*2+0,l,m+0,pos);
upd(v*2+1,m+1,r,pos);
t[v]=min(t[v*2+0],t[v*2+1]);
}
pair<int,int> que(int v, int l, int r, int ql, int qr) {
if(r<ql || qr<l) return {1e9,1e9};
if(ql<=l && r<=qr) return t[v];
int m=(l+r)/2;
return min(que(v*2+0,l,m+0,ql,qr),que(v*2+1,m+1,r,ql,qr));
}
void add(int p, pair<int,int> val) {
S[p].insert(val);
upd(1,1,2*N,p);
}
void del(int p, pair<int,int> val) {
S[p].erase(val);
upd(1,1,2*N,p);
}
void prep() {
for(int i=1;i<MX;i++) {
S[i].insert({1e9,1e9});
}
for(int i=1;i<4*MX;i++) {
t[i]={1e9,1e9};
}
}
} st;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>Q;
for(int i=1;i<=N;i++) {
cin>>L[i]>>R[i];
id[L[i]]=0;
id[R[i]]=0;
}
int cnt=1;
for(auto &[x,y]:id) y=cnt++;
for(int i=1;i<=N;i++) {
L[i]=id[L[i]];
R[i]=id[R[i]];
open[R[i]].push_back({L[i],i});
cl[L[i]].push_back({R[i],i});
}
st.prep();
for(int r=2*N;r>=1;r--) {
for(auto [l,id]:open[r]) {
st.add(r,make_pair(l,id));
}
for(auto [R,id]:cl[r]) {
st.del(R,make_pair(r,id));
int qry=st.que(1,1,2*N,r,R).second;
if(qry!=1e9) up[id][0]=qry;
st.add(R,make_pair(r,id));
}
for(auto [R,id]:cl[r]) {
st.del(R,make_pair(r,id));
}
}
for(int k=0;k+1<20;k++) {
for(int i=1;i<=N;i++) {
if(up[i][k]!=0 && up[up[i][k]][k]!=up[i][k])
up[i][k+1]=up[up[i][k]][k];
}
}
for(int i=0;i<Q;i++) {
int s,e;
cin>>s>>e;
if(s==e) {
cout<<0<<'\n';
continue;
}
int cur=e, res=0;
for(int k=19;k>=0;k--) {
if(up[cur][k]!=0 && L[up[cur][k]]>R[s]) {
cur=up[cur][k];
res+=1<<k;
}
}
if(L[cur]<=R[s] && R[s]<=R[cur]) {
res++;
cout<<res<<'\n';
continue;
}
cur=up[cur][0];
res++;
if(L[cur]<=R[s] && R[s]<=R[cur]) {
res++;
cout<<res<<'\n';
} else {
cout<<"impossible"<<'\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... |