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;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
const int INF = 1e18;
int succ[maxn][18];
struct info{
int l, r, id;
info(){}
info(int _l, int _r, int _id) : l(_l), r(_r), id(_id){}
bool operator < (const info& other) const{
return r < other.r;
}
};
vector<int> val;
int getid(int x){ return lower_bound(val.begin(), val.end(), x) - val.begin();}
pll st[maxn * 4];
pll op(pll a, pll b){
if(a.f < b.f) return a;
return b;
}
void upd(int pos, int val, int id, int v = 1, int l = 0, int r = maxn - 1){
if(l == r){
if(st[v].f > val) st[v] = {val, id};
return;
}
int m = (l + r) / 2;
if(pos <= m) upd(pos, val, id, v * 2, l, m);
else upd(pos, val, id, v * 2 + 1, m + 1, r);
st[v] = op(st[v * 2], st[v * 2 + 1]);
}
pll qry(int l, int r, int v = 1, int L = 0, int R = maxn - 1){
if(l > R || r < L) return {INF, -1};
if(l <= L && r >= R) return st[v];
int m = (L + R) / 2;
return op(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
signed main(void){
fastio;
int n, q;
cin>>n>>q;
for(int i = 0; i < maxn * 4; i++) st[i] = {INF, -1};
vector<info> e(n), c(n);
for(int i = 0; i < n; i++){
int l, r;
cin>>l>>r;
val.pb(l), val.pb(r);
e[i] = info(l, r, i);
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
for(int i = 0; i < n; i++) e[i].l = getid(e[i].l), e[i].r = getid(e[i].r);
c = e;
sort(e.begin(), e.end());
for(int i = 0; i < n; i++){
int t = e[i].r;
int tmp = i;
while(tmp < n && e[tmp].r == t){
upd(e[tmp].r, e[tmp].l, e[tmp].id);
tmp++;
}
while(i < n && e[i].r == t){
succ[e[i].id][0] = qry(e[i].l, e[i].r).s;
if(succ[e[i].id][0] == -1) succ[e[i].id][0] = e[i].id;
i++;
}
i--;
}
for(int i = 0; i < n; i++){
for(int j = 1; j < 18; j++) succ[i][j] = succ[succ[i][j - 1]][j - 1];
}
while(q--){
int s, t;
cin>>s>>t;
s--, t--;
if(s == t){
cout<<0<<"\n";
continue;
}
if(c[s].r >= c[t].l && c[s].r <= c[t].r){
cout<<1<<"\n";
continue;
}
int ans = 0;
for(int i = 17; i >= 0; i--){
if(c[succ[t][i]].l > c[s].r) t = succ[t][i], ans += (1 << i);
}
if(c[succ[t][0]].l <= c[s].r && c[succ[t][0]].r >= c[s].r) cout<<ans + 2<<"\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... |