Submission #926530

#	Time	Username	Problem	Language	Result	Execution time	Memory
926530		andrei_boaca	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	209 ms	39368 KiB

event2

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int INF=1e9+5;
int n,k,where[100005],nxt[100005],dp[21][100005],loga[100005];
int rmq[21][100005];
struct date
{
    int l,r,ind;
} v[100005];
bool byr(date a, date b)
{
    return a.r<b.r;
}
map<pii,int> f;
set<pii> setik;
int getval(int st,int dr)
{
    int rez=0;
    for(int i=18;i>=0;i--)
        if(dp[i][st]<=n&&v[dp[i][st]].r<=v[dr].l)
        {
            rez+=(1<<i);
            st=dp[i][st];
        }
    return rez;
}
int getmax(int l,int r)
{
    int lg=loga[r-l+1];
    return max(rmq[lg][l],rmq[lg][r-(1<<lg)+1]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].l>>v[i].r;
        v[i].ind=i;
    }
    sort(v+1,v+n+1,byr);
    int r=0;
    int jaxi=0;
    for(int i=1;i<=n;i++)
    {
        if(v[i].l>=r)
        {
            r=v[i].r;
            jaxi++;
        }
    }
    if(jaxi<k)
    {
        cout<<-1;
        return 0;
    }
    v[0]={0,0,0};
    v[n+1]={INF,INF,n+1};
    for(int i=0;i<=n+1;i++)
        rmq[0][i]=v[i].l;
    for(int i=1;i<=n+1;i++)
    {
        for(int bit=0;bit<=20;bit++)
            if((1<<bit)<=i)
                loga[i]=bit;
    }
    for(int j=1;j<=18;j++)
        for(int i=0;i<=n+1;i++)
        {
            rmq[j][i]=rmq[j-1][i];
            int poz=i+(1<<(j-1));
            if(poz<=n+1)
                rmq[j][i]=max(rmq[j][i],rmq[j-1][poz]);
        }
    nxt[n+1]=n+1;
    for(int i=0;i<=n+1;i++)
    {
        where[v[i].ind]=i;
        /*for(int j=i+1;j<=n+1;j++)
            if(v[j].l>=v[i].r)
            {
                nxt[i]=j;
                break;
            }*/
        int st=i+1;
        int dr=n+1;
        nxt[i]=n+1;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(getmax(i+1,mij)>=v[i].r)
            {
                nxt[i]=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
    }
    for(int i=0;i<=n+1;i++)
        dp[0][i]=nxt[i];
    for(int j=1;j<=18;j++)
        for(int i=0;i<=n+1;i++)
            dp[j][i]=dp[j-1][dp[j-1][i]];
    f[{0,n+1}]=jaxi;
    int have=jaxi;
    setik.insert({0,n+1});
    vector<int> sol;
    for(int who=1;who<=n&&sol.size()<k;who++)
    {
        int poz=where[who];
        auto it=prev(setik.upper_bound({poz,0}));
        int st=(*it).first;
        int dr=(*it).second;
        if(v[st].r<=v[poz].l&&v[poz].r<=v[dr].l)
        {
            int add=-f[{st,dr}];
            add+=getval(st,poz);
            add+=getval(poz,dr);
            add++;
            if(have+add>=k)
            {
                have+=add;
                setik.erase(it);
                setik.insert({st,poz});
                setik.insert({poz,dr});
                f[{st,poz}]=getval(st,poz);
                f[{poz,dr}]=getval(poz,dr);
                sol.push_back(who);
            }
        }
    }
    for(int i:sol)
        cout<<i<<'\n';
    return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:112:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |     for(int who=1;who<=n&&sol.size()<k;who++)
      |                           ~~~~~~~~~~^~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61