Submission #1074326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074326		MOUF_MAHMALAT	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	3096 ms	5096 KiB

event2

#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
#define F first
#define S second
using namespace std;
typedef int ll;
typedef pair<ll,ll>pll;
const ll oo= 1e5+9;
const ll inf=2e9+9;
struct node
{
    ll l,r,t;
} a[oo];
bool cmp(const node&A,const node&B)
{
    return A.l<B.l;
}
ll n,k,id[oo],dp[oo],mx[oo],nxt[oo];
bool vis[oo];
void solve()
{
    cin>>n>>k;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i].l>>a[i].r;
        a[i].t=i;
    }
    sort(a+1,a+n+1,cmp);
    dp[n+1]=mx[n+1]=-inf;
    for(ll i=1; i<=n; i++)
    {
        nxt[i]=n+1;
        for(ll j=i+1; j<=n; j++)
            if(a[i].r<=a[j].l)
            {
                nxt[i]=j;
                break;
            }
    }
    for(ll i=1; i<=n; i++)
        id[a[i].t]=i;
//    for(ll i=1;i<=n;i++)
//    {
//        cout<<a[i].l<<" "<<a[i].r<<"\n";
//    }
    vector<ll>ans;
    for(ll i=1; i<=n&&k; i++)
    {
        if(vis[id[i]])
            continue;
        for(ll j=n; j>=id[i]; j--)
        {
            if(vis[j])
                dp[j]=-inf;
            else
                dp[j]=max(1,1+mx[nxt[j]]);
            mx[j]=max(dp[j],mx[j+1]);
        }
        for(ll j=n;j>id[i];j--)
          mx[j]=dp[j]=-inf;
        for(ll j=id[i]-1;j;j--)
        {
            if(vis[j])
                dp[j]=-inf;
            else
                dp[j]=mx[nxt[j]]+1;
            mx[j]=max(dp[j],mx[j+1]);
        }
        vis[id[i]]=1;
//        cout<<i<<" :\n";
//        cout<<mx[1]<<"\n";
        if(mx[1]>=k)
        {
            ll x=id[i];
            ans.push_back(i);
            k--;
            for(ll j=1;j<=n;j++)
            {
                if(vis[j])
                    continue;
                if(max(a[x].l,a[j].l)<min(a[x].r,a[j].r))
                    vis[j]=1;
            }
        }
    }
//    for(auto&z:ans)
//        cout<<z<<" ";
//    cout<<"\n";
    if(k)
        cout<<"-1";
    else
        for(auto&z:ans)
        cout<<z<<"\n";
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    ll tt=1;
//    cin>>tt;
    while(tt--)
        solve();
    return 0;
}

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