Submission #417206

#	Time	Username	Problem	Language	Result	Execution time	Memory
417206		lyc	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	133 ms	36540 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 lx, ly, rx, ry, v; // end earliest, start latest
};
 
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.rx, b.ly, a.rx, b.ly, a.v+b.v };
        if (SZ(itv)) {
            if (ret.v == 0) {
                ret = { 
                    itv[0].first, itv[0].second,
                    itv.back().first, itv.back().second,
                    1
                };
            } else {
                auto it = lower_bound(ALL(itv), ii(a.ly,0));
                auto it2 = lower_bound(ALL(itv), ii(a.ry,0));
                if (it != itv.end() && it->second <= b.rx) {
                    ++ret.v;
                    ret.lx = ret.rx = a.lx;
                    ret.ly = ret.ry = b.ry;
                } else return ret;

                if (it2 != itv.end() && it2->second <= b.lx) {
                    ret.lx = ret.rx = a.rx;
                    ret.ly = ret.ry = b.ly;
                    return ret;
                }

                if (it != itv.end() && it->second <= b.lx) {
                    ret.ly = min(ret.ly, b.ly);
                }

                if (it2 != itv.end() && it2->second <= b.rx) {
                    ret.rx = max(ret.rx, a.rx);
                }
            }
        }

        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();

            sort(ALL(itv));
            vector<ii> tmp;
            for (auto& x : itv) {
                if (tmp.empty() || tmp.back().second < x.second) {
                    tmp.push_back(x);
                }
            }
            itv = tmp;

            res = merge(l->res, r->res);
            //cout << s _ e _ "v" _ res.v _ "itv: ";
            //for (auto& x : itv) {
            //    cout << vals[x.first] _ vals[x.second] << ", ";
            //}
            //cout << endl;
        }
    }
 
    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