Submission #986829

#	Time	Username	Problem	Language	Result	Execution time	Memory
986829		alexdd	Event Hopping (BOI22_events)	C++17	20 / 100	250 ms	47704 KiB

events

#include<iostream>
#include<map>
#include<vector>
using namespace std;
pair<int,int> aib[200005];
pair<int,int> qry(int poz)
{
    pair<int,int> aux={0,0};
    for(int i=poz;i<=200002;i+=(i&(-i)))
        aux = max(aux, aib[i]);
    return aux;
}
void upd(int poz, pair<int,int> newv)
{
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] = max(aib[i], newv);
}

int n,q,cate;
map<int,int> mp,nrm;
pair<int,int> e[100005];
vector<int> caple[200005],capri[200005];
int nxt[100005][17];
void calc_nxt()
{
    for(int i=1;i<=n;i++)
    {
        caple[e[i].first].push_back(i);
        capri[e[i].second].push_back(i);
    }
    for(int i=1;i<=cate;i++)
    {
        for(auto x:caple[i])
            upd(e[x].first,{e[x].second,x});
        for(auto x:capri[i])
            nxt[x][0] = qry(e[x].first).second;
    }
    //for(int i=1;i<=n;i++) cout<<i<<" "<<nxt[i][0]<<" nxt\n";
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            nxt[i][p] = nxt[nxt[i][p-1]][p-1];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q;
    int le,ri;
    for(int i=1;i<=n;i++)
    {
        cin>>le>>ri;
        e[i]={le,ri};
        mp[le]++;
        mp[ri]++;
    }
    for(auto it:mp) nrm[it.first]=++cate;
    for(int i=1;i<=n;i++) e[i] = {nrm[e[i].first],nrm[e[i].second]};
    calc_nxt();
    while(q--)
    {
        cin>>le>>ri;
        if(le==ri)
        {
            cout<<0<<"\n";
            continue;
        }
        if(e[ri].second < e[le].second)
        {
            cout<<"impossible\n";
            continue;
        }
        if(e[ri].first <= e[le].second)
        {
            cout<<1<<"\n";
            continue;
        }
        int cnt=2;
        for(int i=16;i>=0;i--)
        {
            if(e[nxt[le][i]].second < e[ri].first)
            {
                le = nxt[le][i];
                cnt += (1<<i);
            }
        }
        le = nxt[le][0];
        if(e[ri].first <= e[le].second && e[le].second <= e[ri].second)
            cout<<cnt<<"\n";
        else
            cout<<"impossible\n";
    }
    return 0;
}

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