Submission #789139

#	Time	Username	Problem	Language	Result	Execution time	Memory
789139		winter0101	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	135 ms	29156 KiB

event2

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
struct line{
int l,r,id;
bool operator < (const line &p)const {
return r<p.r;
}
}a[maxn];
int st[maxn][21];
vector<int>del[maxn];
int suf[maxn];
int pos[maxn];
struct cus{
int u;
bool operator < (const cus &p)const {
return pos[u]<pos[p.u];
}
};
int p[maxn];
int f[maxn];
int afs[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n,k;
    cin>>n>>k;
    for1(i,1,n){
    cin>>a[i].l>>a[i].r;
    a[i].id=i;
    }
    sort(a+1,a+1+n);
    for1(i,1,n){
    pos[a[i].id]=i;
    int l=1,r=i-1,ans=0;
    while (l<=r){
        int mid=(l+r)/2;
        if (a[mid].r<=a[i].l){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    del[ans].pb(i);
    f[i]=1+p[ans];
    p[i]=max(p[i-1],f[i]);
    f[i]--;
    }
    set<int>num;
    for1(i,1,n+1)num.insert(i);
    for1(i,0,0){
    for (auto v:del[i]){
        num.erase(v);
    }
    }
    st[n+1][0]=n+1;
    a[n+1].l=a[n+1].r=1e9+1;
    for1(i,1,n){
    st[i][0]=*(num.begin());
    for (auto v:del[i]){
        num.erase(v);
    }
    }
    for1(j,1,20){
    for1(i,1,n+1){
    st[i][j]=st[st[i][j-1]][j-1];
    }
    }
    set<int>best;
    set<int>::iterator it2;
    best.insert(0);
    for2(i,n,1){
    for (auto v:del[i]){
        best.insert(suf[v]);
    }
    it2=best.end();
    it2--;
    suf[i]=(*it2)+1;
    }
    for1(i,1,n){
    suf[i]--;
    }
    int maxnum=0;
    multiset<cus>t;
    multiset<cus>::iterator it;
    for1(i,1,n){
    if (sz(t)==k){
        //cout<<"vai l";
        break;
    }
    if (t.empty()){
        int id=pos[i];
        if (f[id]+1+suf[id]>=k){
            t.insert({i});
            maxnum=f[id]+1+suf[id];
        }
        continue;
    }
    else {
        it=t.upper_bound({i});
        int nw=maxnum;
        //if (i==3)cout<<maxnum<<" "<<k<<'\n';
        if (it==t.end()){
            it--;
            //cout<<maxnum<<'\n';
            int id1=pos[(*it).u];
            if (a[id1].r>a[pos[i]].l)continue;
            nw-=suf[id1];
            nw++;
            nw+=suf[pos[i]];
            //if (i==3)cout<<nw<<'\n';
            int u=id1;
            //if (i==3)cout<<st[id1][20]<<'\n';
            for2(j,20,0){
            int id2=st[u][j];
            if (a[id2].r<=a[pos[i]].l){
                nw+=(1<<j);
                u=st[u][j];
            }
            }
            if (nw>=k){
                t.insert({i});
                maxnum=nw;
            }
            continue;
        }
        else if (it==t.begin()){
            int id1=pos[(*it).u];
            if (a[pos[i]].r>a[id1].l)continue;
            nw-=f[id1];
            nw++;
            nw+=f[pos[i]];
            int u=pos[i];
            for2(j,20,0){
            int id2=st[u][j];
            if (a[id2].r<=a[id1].l){
                nw+=(1<<j);
                u=st[u][j];
            }
            }
            if (nw>=k){
                t.insert({i});
                maxnum=nw;
            }
            continue;
        }
        else {
           int id2=pos[(*it).u];
           it--;
           int id1=pos[(*it).u];
           if (a[id1].r>a[pos[i]].l)continue;
           if (a[pos[i]].r>a[id2].l)continue;
           int u=id1;
           for2(j,20,0){
           int id3=st[u][j];
           if (a[id3].r<=a[id2].l){
            nw-=(1<<j);
            u=st[u][j];
           }
           }
           nw++;
           u=id1;
           for2(j,20,0){
           int id3=st[u][j];
           if (a[id3].r<=a[pos[i]].l){
            nw+=(1<<j);
            u=st[u][j];
           }
           }
           u=pos[i];
           for2(j,20,0){
           int id3=st[u][j];
           if (a[id3].r<=a[id2].l){
            nw+=(1<<j);
            u=st[u][j];
           }
           }
           if (nw>=k){
            t.insert({i});
            maxnum=nw;
           }
           continue;
        }
    }
    }
    //cout<<maxnum;
    if (sz(t)<k){
        cout<<-1;
        return 0;
    }
    vector<int>as;
    for(auto v:t)as.pb(v.u);
    sort(all(as));
    for (auto v:as)cout<<v<<'\n';




}

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