Submission #575275

#	Time	Username	Problem	Language	Result	Execution time	Memory
575275		balbit	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	430 ms	76804 KiB

event2

#include <bits/stdc++.h>
using namespace std;
//#undef BALBIT
#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];
vector<seg> S2[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});
            S2[o].pb({l,l,0});
        }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});
            }
        }else if (dp[i].f == big-1) {
            if (SZ(S2[o]) == 0 || dp[i].s > S2[o].back().l) {
                S2[o].pb({dp[i].s, i, big-1});
            }
        }
    }

//    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) {
        bug(l,r,SZ(S[o]));
        bug(S[o][0].r);
        bug(now.l, now.cnt);
        // important!
        int x = now.l;
        if (x < S[o][0].r) {
            // two choices
            bug("up");
            seg oldnow = now;
            seg now1 = S[o].back(); now1.cnt += now.cnt-1;

            if (now1 > now) now = now1;
            if (SZ(S2[o]) && x >= S2[o][0].r) {
                int bl = 0, br = SZ(S2[o]);
                while (bl != br) {
                    int bmd = (bl + br) / 2;
                    if (S2[o][bmd].r <= x) {
                        // ok!
                        bl = bmd + 1;
                    }else{
                        br = bmd;
                    }
                }
                --bl;
                seg now1 = S2[o][bl]; now1.cnt += oldnow.cnt;
                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;
        }
        bug(now.l, now.cnt);
        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 (l == 3 && r == 6) {
        bug(now.l, now.cnt);
    }
    if (now.l < l-1) return now.cnt-1;
    return now.cnt;
}

int 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);
    bug(yom(rngL, rngR));
    bug(yom(rngL, v[x].f));
    bug(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(yom(3,6));



    #ifdef BALBIT
    for (int i = 0; i<SZ(xpos); ++i) {
        for (int j = i; j<SZ(xpos); ++j) {
            bug(i,j,yom(i,j));
        }
    }
    #endif

//    k = max(0, curcnt - 0);
    bug(k);

    bug(curcnt);
    if (curcnt < k) {
        cout<<-1<<endl; return 0;
    }

    vector<int> took;
    for (int i = 0; i<n; ++i) {
        int tr = tryrem(i);
        bug(i, tr);
        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;
    }


}

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