제출 #1077426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1077426		LIF	Event Hopping (BOI22_events)	C++14	40 / 100	1581 ms	5116 KiB

events

#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;
        }
    }
    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;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30