Submission #575269

#	Time	Username	Problem	Language	Result	Execution time	Memory
575269		balbit	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	268 ms	49680 KiB

event2

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
 
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
 
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
 
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
 
#endif // BALBIT
 
const int maxn = 2e5+5;
 
 
pii v[maxn];
 
struct seg{
    int l, r, cnt;
    bool operator > (seg o)  { // bigger is better
        return cnt != o.cnt? cnt > o.cnt : l > o.l;
    }
};
 
vector<int> here[maxn];
vector<seg> S[maxn*4];
 
 
pair<int, int> dp[maxn];
 
void build(int o = 1, int l = 0, int r = maxn-1) {
    if (l == r) {
        sort(ALL(here[l]));
        if (SZ(here[l])) {
            S[o].pb({here[l].back(), l, 1});
        }else{
            S[o].pb({l, l, 0}); // not entirely sure
        }
        return;
    }
    int mid = (l+r)/2;
    build(o*2,l,mid); build(o*2+1, mid+1, r);
 
    int big = 0;
 
    FOR(i,l,r+1) {
        dp[i] = {0, l};
        if (i > l) MX(dp[i], dp[i-1]);
        for (int lp : here[i]) {
            if (lp < l) {
                MX(dp[i], make_pair(1,lp));
            }else{
                pii go = dp[lp]; ++go.f;
                MX(dp[i], go);
            }
        }
        MX(big, dp[i].f);
    }
 
    FOR(i,l,r+1) {
        if (dp[i].f == big) {
            if (SZ(S[o]) == 0 || dp[i].s > S[o].back().l) {
                S[o].pb({dp[i].s, i, big});
            }
        }
    }
 
    if (SZ(S[o]) > 1) {
        bug(o, l,r);
        for (auto c : S[o]) {
            bug(c.l, c.r, c.cnt);
        }
    }
}
 
seg now = {maxn+1, maxn+1, 0};
 
void QU(int L, int R, int o=1, int l=0, int r = maxn-1) {
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        // important!
        int x = now.l;
        if (x < S[o][0].r) {
            // two choices
            seg now1 = S[o].back(); now1.cnt += now.cnt-1;
            if (now1 > now) now = now1;
        }else{
            int bl = 0, br = SZ(S[o]);
            while (bl != br) {
                int bmd = (bl + br) / 2;
                if (S[o][bmd].r <= x) {
                    // ok!
                    bl = bmd + 1;
                }else{
                    br = bmd;
                }
            }
            --bl;
            seg now1 = S[o][bl]; now1.cnt += now.cnt;
            if (now1 > now) now = now1;
        }
        return;
    }
    int mid = (l+r)/2;
    QU(L,R,o*2+1,mid+1,r);
    QU(L,R,o*2,l,mid);
}
 
int yom(int l, int r) {
    now = {maxn+1, maxn+1, 0};
    QU(l,r);
    if (now.l < l-1) return now.cnt-1;
    return now.cnt;
}
 
ll curcnt = 0;
 
set<pii> st;
 
int tryrem(int x) {
    auto it = st.lower_bound(v[x]);
    if (it != st.end() && v[x].s > it->f) return -maxn;
    if (it != st.begin() && v[x].f < prev(it)->s) {
        return -maxn;
    }
    int rngL = it==st.begin()?0 : (prev(it) -> s + 1);
    int rngR = it==st.end()  ?maxn-1 : it -> f;
    bug(v[x].f, v[x].s, rngL, rngR);
    int yoink =  curcnt - yom(rngL, rngR) + yom(rngL, v[x].f) + yom(v[x].s+1, rngR);
    return yoink;
}
 
signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
 
    bug(1,2);
 
    int n,k; cin>>n>>k;
 
    vector<int> xpos;
 
    REP(i,n) {
        cin>>v[i].f>>v[i].s;
        xpos.pb(v[i].f); xpos.pb(v[i].s);
    }
    sort(ALL(xpos));
    xpos.resize(unique(ALL(xpos)) - xpos.begin());
 
    REP(i, n) {
        pii &p = v[i];
        p.f = lower_bound(ALL(xpos), p.f) - xpos.begin();
        p.s = lower_bound(ALL(xpos), p.s) - xpos.begin();
        bug(p.f, p.s);
        here[p.s].pb(p.f);
    }
 
    build();
    curcnt = S[1][0].cnt;
 
    bug(curcnt);
    if (curcnt < k) {
        cout<<-1<<endl; return 0;
    }
 
    vector<int> took;
    for (int i = 0; i<n; ++i) {
        int tr = tryrem(i);
        if (tr + 1 + SZ(took) >= k) {
            // ok!
            took.pb(i);
            bug(i);
            curcnt = tr;
            st.insert(v[i]);
        }else{
 
        }
    }
 
    if (k <= SZ(took)) {
        REP(i,k) cout<<took[i]+1<<endl;
    }else{
        cout<<-1<<endl;
    }
 
 
}

Compilation message (stderr)

event2.cpp: In function 'void build(int, int, int)':
event2.cpp:85:19: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   85 |         for (auto c : S[o]) {
      |                   ^

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