이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005],go[500005];
struct mn
{
int val;
int id;
}minn[800005];
struct nod
{
int ll;
int rr;
int id;
}node[500005];
bool cmp(nod x,nod y)
{
if(x.rr == y.rr)return x.ll < y.ll;
else return x.rr < y.rr;
}
int read()
{
int x=0,f=1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<3) + (x<<1) + (ch-'0');
ch = getchar();
}
return x*f;
}
void pushup(int rt)
{
if(minn[rt<<1].val < minn[rt<<1|1].val)
{
minn[rt].val = minn[rt<<1].val;
minn[rt].id = minn[rt<<1].id;
}
else
{
minn[rt].val = minn[rt<<1|1].val;
minn[rt].id = minn[rt<<1|1].id;
}
return;
}
pair<int,int> query(int l,int r,int queryl,int queryr,int rt)
{
if(queryl <= l && r <= queryr)
{
return make_pair(minn[rt].val,minn[rt].id);
}
int mid = (l+r)>>1;
pair<int,int> fir = make_pair(2e9,-1);
if(mid >= queryl)
{
auto pp = query(l,mid,queryl,queryr,rt<<1);
if(pp.first < fir.first)fir = pp;
}
if(mid + 1 <= queryr)
{
auto pp = query(mid+1,r,queryl,queryr,rt<<1|1);
if(pp.first < fir.first)fir = pp;
}
return fir;
}
void build(int l,int r,int rt)
{
if(l == r)
{
minn[rt].val = node[l].ll;
minn[rt].id = l;
return;
}
int mid = (l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
return;
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
l[i] = read();r[i] = read();
nod temp = nod{l[i],r[i],i};
node[i] = temp;
}
sort(node+1,node+n+1,cmp);
build(1,n,1);
for(int i=1;i<=n;i++)
{
go[i] = -1;
int ll = 1,rr = i-1,last = -1;
while (ll<=rr)
{
int mid = (ll+rr)>>1;
if(node[mid].rr >= node[i].ll)
{
last = mid;
rr = mid - 1;
}
else ll = mid + 1;
}
if(last <= 0)go[i] = -1;
else
{
auto pp = query(1,n,last,i-1,1);
go[i] = pp.second;
}
}
// for(int i=1;i<=n;i++)
// {
// cout<<node[i].ll<<" "<<node[i].rr<<endl;
// }
// cout<<endl;
// for(int i=1;i<=n;i++)
// {
// cout<<go[i]<<" ";
// }
// cout<<endl;
while(q--)
{
int s,e;
cin>>s>>e;
if(e == s)
{
cout<<"0"<<endl;
continue;
}
if(l[e] <= r[s] && r[s] <= r[e])
{
cout<<"1"<<endl;
continue;
}
int cnt = 0;
int now = -1;
for(int i=1;i<=n;i++)
{
if(node[i].id == e)
{
now = i;
break;
}
}
bool can = false;
while(now != -1)
{
int ll = node[now].ll;
int rr = node[now].rr;
if(ll <= r[s] && r[s] <= rr)
{
cnt++;
can = true;
break;
}
now = go[now];
cnt++;
}
if(can == true)cout<<cnt<<endl;
else cout<<"impossible"<<endl;
}
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... |