이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MAXM 20
int n,q;
int l[MAXN],r[MAXN];
vector<int> kompresija;
vector<pair<pair<int,int>,int>> queries;
pair<int,int> seg[MAXN*8];
int parent[MAXM][MAXN];
pair<int,int> mergee(pair<int,int> x,pair<int,int> y)
{
if (x.first>y.first) return x;
return y;
}
void update(int node,int l,int r,int pos,pair<int,int> val)
{
if (l==r) seg[node]=val;
else
{
int mid=(l+r)/2;
if (pos<=mid) update(2*node,l,mid,pos,val);
else update(2*node+1,mid+1,r,pos,val);
seg[node]=mergee(seg[2*node],seg[2*node+1]);
}
}
pair<int,int> query(int node,int l,int r,int a,int b)
{
if (a>b) return {0,0};
if (l==a and r==b) return seg[node];
int mid=(l+r)/2;
return mergee(query(2*node,l,mid,a,min(b,mid)),query(2*node+1,mid+1,r,max(a,mid+1),b));
}
int main()
{
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>l[i]>>r[i];
kompresija.push_back(l[i]);
kompresija.push_back(r[i]);
}
sort(kompresija.begin(),kompresija.end());
kompresija.erase(unique(kompresija.begin(),kompresija.end()),kompresija.end());
for (int i=1;i<=n;i++)
{
l[i]=lower_bound(kompresija.begin(),kompresija.end(),l[i])-kompresija.begin();
r[i]=lower_bound(kompresija.begin(),kompresija.end(),r[i])-kompresija.begin();
}
for (int i=1;i<=n;i++) queries.push_back({{l[i],r[i]},i});
sort(queries.begin(),queries.end());
for (int i=0;i<n;i++) update(1,0,2*MAXN-1,queries[i].first.first,{queries[i].first.second,queries[i].second});
for (int i=0;i<n;i++)
{
pair<int,int> sol=query(1,0,2*MAXN-1,0,queries[i].first.second);
if (sol.second==queries[i].second) continue;
if (sol.first==0 and sol.second==0) continue;
if (sol.first>=queries[i].first.second) parent[0][queries[i].second]=sol.second;
}
for (int j=1;j<MAXM;j++)
{
for (int i=1;i<=n;i++) parent[j][i]=parent[j-1][parent[j-1][i]];
}
for (int i=1;i<=q;i++)
{
int node1,node2;cin>>node1>>node2;
if (node1==node2) {cout<<0<<endl;continue;}
if (!(r[node1]<=r[node2])) {cout<<"Impossible"<<endl;continue;}
if (l[node2]<=r[node1]) {cout<<1<<endl;continue;}
int node=node1,ans=0;
for (int j=MAXM-1;j>=0;j--)
{
if (parent[j][node]==0) continue;
if (l[node2]>r[parent[j][node]] and r[parent[j][node]]<=r[node2]) {ans+=(1<<j);node=parent[j][node];}
}
node=parent[0][node];ans++;
if (node==0) {cout<<"Impossible"<<endl;continue;}
if (node2==node) cout<<ans<<endl;
else if (l[node2]<=r[node] and r[node]<=r[node2]) cout<<ans+1<<endl;
else cout<<"Impossible"<<endl;
}
}
# | 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... |