이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 2e5 + 5;
const int LOG = 20;
int fw[N];
void upd(int c,int u){
for(;c<N;c+=c&-c) fw[c]=max(fw[c],u);
}
int query(int c,int res=0LL){
for(;c;c-=c&-c) res=max(res,fw[c]);
return res;
}
void _(){
int n,q;
cin >> n >> q;
vector<array<int,2>> v(n+5);
vector<int> zip;
for(int i=1;i<=n;i++){
int l,r;
cin >> l >> r;
v[i]={l,r};
zip.push_back(l);
zip.push_back(r);
}
sort(all(zip));
zip.erase(unique(all(zip)),zip.end());
for(int i=1;i<=n;i++){
v[i][0]=(lower_bound(all(zip),v[i][0])-zip.begin())+1;
v[i][1]=(lower_bound(all(zip),v[i][1])-zip.begin())+1;
}
vector<int> events;
for(int i=1;i<=n;i++) events.push_back(i);
sort(all(events),[&](int a,int b){
return v[a][1]<v[b][1];
});
vector<int> ans(q+5,-1);
vector<array<int,3>> queries;
for(int i=1;i<=q;i++){
int a,b;
cin >> a >> b;
queries.push_back({a,b,i});
}
sort(all(queries),[&](array<int,3> a,array<int,3> b){
return v[a[1]][1]<v[b[1]][1];
});
int p = 0;
for(auto x:queries){
// cout << x[0] << ' ' << x[1] << ' ' << x[2] << '\n';
int a = x[0], b = x[1], ind = x[2];
if(a==b){
ans[ind]=0;
continue;
}
while(p<n && v[events[p]][1]<=v[b][1]){
upd(v[events[p]][0],v[events[p]][1]);
p++;
}
if(v[a][1]>v[b][1]) continue;
bool no = 0;
int res = 1, gec = v[a][1];
while(gec<v[b][0]){
int hmhm = query(gec);
if(hmhm<=gec){
no=1;
break;
}
gec=hmhm;
res++;
}
if(!no) ans[ind]=res;
}
for(int i=1;i<=q;i++){
if(ans[i]==-1) cout << "Impossible\n";
else cout << ans[i] << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# | 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... |