oj.uz

Submission #789129

# Submission time Handle Problem Language Result Execution time Memory
789129 2023-07-21T05:53:32 Z winter0101 Event Hopping 2 (JOI21_event2) C++14
0 / 100
 73 ms 27548 KB 
#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];
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;
    for1(i,1,n){
    st[i][0]=*(num.begin());
    }
    for1(j,1,20){
    for1(i,1,n){
    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)break;
    if (t.empty()){
        int id=pos[i];
        if (f[id]+1+suf[id]>=k){
            t.insert({i});
            maxnum=f[id]+1+suf[id];
        }
        else {
            continue;
        }
    }
    else {
        it=t.upper_bound({i});
        int nw=maxnum;
        if (it==t.end()){
            it--;
            int id1=pos[(*it).u];
            if (a[id1].r>a[pos[i]].l)continue;
            nw-=suf[id1];
            nw++;
            nw+=suf[pos[i]];
            int u=(*it).u;
            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;
        }
    }
    }
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Incorrect 73 ms 27548 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 2 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 2684 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Incorrect 2 ms 2644 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Incorrect 73 ms 27548 KB Output isn't correct
5 Halted 0 ms 0 KB -