Submission #417055

#	Time	Username	Problem	Language	Result	Execution time	Memory
417055		lyc	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	170 ms	41076 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int mxN = 1e5+5;
const int mxK = 1e5+5;

int N, K;
struct Event { int L, R, I; };
vector<Event> events;
vector<int> vals;
int used[mxN], ans[mxK];

struct Result {
    int x, y, v;
};

struct node {
    int s, e, m;
    Result res;
    vector<ii> itv;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    Result merge(Result a, Result b) {
        Result ret = { a.v + b.v, a.x, b.y };
        auto it = lower_bound(ALL(itv), ii(a.y,0));
        if (it != itv.end() && it->second <= b.x) ++ret.v;
        return ret;
    }

    void update(int a, int b) {
        if (a < s || e < b) return;
        if (b <= m) l->update(a,b);
        else if (a > m) r->update(a,b);
        else itv.push_back(ii(a,b));
    }

    void build() {
        if (s == e) {
            res = { s, s, SZ(itv) > 0 };
        } else {
            l->build();
            r->build();
            res = merge(l->res, r->res);
        }
    }

    Result query(int a, int b) {
        if (a <= s && e <= b) return res;
        else if (b <= m) return l->query(a,b);
        else if (a > m) return r->query(a,b);
        else {
            auto r1 = l->query(a,m);
            auto r2 = r->query(m+1,b);
            return merge(r1, r2);
        }
    }
} *root;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;
    FOR(i,1,N){
        int L, R; cin >> L >> R;
        events.push_back({L,R,i});
        vals.push_back(L);
        vals.push_back(R);
    }

    sort(ALL(vals));
    vals.resize(unique(ALL(vals))-vals.begin());
    root = new node(0,SZ(vals));
    for (auto& e : events) {
        e.L = lower_bound(ALL(vals), e.L) - vals.begin();
        e.R = lower_bound(ALL(vals), e.R) - vals.begin();
        root->update(e.L,e.R);
    }
    root->build();

    set<ii> cur;
    cur.insert(ii(-1,-1));
    cur.insert(ii(SZ(vals),SZ(vals)));
    ll take = root->query(0,SZ(vals)).v;
    for (auto& e : events) {
        auto it = cur.lower_bound(ii(e.L, 0));
        if (e.R > it->first) continue;
        if (prev(it)->second > e.L) continue;

        ll take2 = take;
        take2 -= root->query(prev(it)->second, it->first).v;
        take2 += root->query(prev(it)->second, e.L).v;
        take2 += root->query(e.R, it->first).v;
        take2 += 1;

        if (take2 >= K) {
            cur.insert(ii(e.L,e.R));
            take = take2;
            used[e.I] = 1;
        }

        if (SZ(cur)-2 >= K) break;
    }

    if (SZ(cur)-2 < K) {
        cout << -1 << '\n';
        return 0;
    }

    FOR(i,1,N) if (used[i] && K) {
        cout << i << '\n';
        --K;
    }
}

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