Submission #1077538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077538		LIF	Event Hopping (BOI22_events)	C++14	100 / 100	255 ms	20824 KiB

events

#include<bits/stdc++.h>
using namespace std;
int n,q,l[500005],r[500005],go[500005][30],pos[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][0] = -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][0] = -1;
        else
        {
            auto pp = query(1,n,last,i-1,1);
            go[i][0] = pp.second;
        }
    }
    for(int i=1;i<=n;i++)
    {
        pos[node[i].id] = i;
    }
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(go[j][i-1] == -1)
            {
                go[j][i] = -1;
                continue;
            }
            go[j][i] = go[go[j][i-1]][i-1];
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<node[i].ll<<" "<<node[i].rr<<endl;
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<go[i][0]<<" ";
    // }
    // cout<<endl;
    // 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 now = pos[e];
        int ans = 0;
        bool can = true;
        for(int i=20;i>=0;i--)
        {
            int target = go[now][i];
            if(target == -1)continue;
            if(node[target].ll > r[s])
            {
                //cout<<"now: "<<now<<" target: "<<target<<endl;
                now = target;
                ans += pow(2,i);
            }
        }
        if(go[now][0] == -1)
        {
            can = false;
        }
        else
        {
            now = go[now][0];
            ans++;
        }
        //cout<<"last: "<<now<<endl;
        int ll = node[now].ll;
        int rr = node[now].rr;
        if(ll <= r[s] && r[s] <= rr)cout<<ans+1<<endl;
        else cout<<"impossible"<<endl;
    }
 
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:158:14: warning: variable 'can' set but not used [-Wunused-but-set-variable]
  158 |         bool can = true;
      |              ^~~

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