Submission #926527

#	Time	Username	Problem	Language	Result	Execution time	Memory
926527		andrei_boaca	Event Hopping 2 (JOI21_event2)	C++17	32 / 100	3060 ms	6168 KiB

event2

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int INF=1e9+5;
int n,k,dp[100005],where[100005],nxt[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;
    st=nxt[st];
    while(st<=n&&v[st].r<=v[dr].l)
    {
        rez++;
        st=nxt[st];
    }
    return rez;
}
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};
    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;
            }
    }
    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:71:37: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for(int who=1;who<=n&&sol.size()<k;who++)
      |                           ~~~~~~~~~~^~

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