Submission #493417

#	Time	Username	Problem	Language	Result	Execution time	Memory
493417		Jarif_Rahman	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	204 ms	22408 KiB

event2

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+7;

int n, k;
vector<pair<int, int>> events;
vector<int> succ;
vector<vector<int>> anc;

int count(int nd, int lim){
    if(nd == -1) return 0;
    if(events[nd].sc > lim) return 0;
    for(int i = 17; i >= 0; i--){
        if(anc[nd][i] != n && events[anc[nd][i]].sc <= lim) return count(anc[nd][i], lim)+(1<<i);
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    events.resize(n);
    succ.resize(n, -1);
    for(auto &p: events) cin >> p.f >> p.sc;

    vector<pair<int, int>> sth;
    for(int i = 0; i < n; i++){
        sth.pb({events[i].f, i+1});
        sth.pb({events[i].sc, -i-1});
    }
    sort(sth.begin(), sth.end());

    int mn = inf, cur = -1, start = -1, start_end = inf;
    for(int i = (int)sth.size()-1; i >= 0; i--){
        int in = sth[i].sc;
        if(in < 0){
            in*=-1;
            in--;
            if(events[in].sc == start_end) start = min(start, in);
            else if(events[in].sc < start_end) start_end = events[in].sc, start = in;
            succ[in] = cur;
        }
        else{
            in--;
            if(events[in].sc == mn) cur = min(cur, in);
            else if(events[in].sc < mn) mn = events[in].sc, cur = in;
        }
    }

    anc.resize(n+1, vector<int>(18, n));
    for(int i = 0; i < n; i++) if(succ[i] != -1) anc[i][0] = succ[i];
    for(int p = 1; p < 18; p++) for(int i = 0; i <= n; i++)
        anc[i][p] = anc[anc[i][p-1]][p-1];

    int sum = count(start, inf);
    set<array<int, 4>> ss;
    ss.insert({inf, 0, start, sum});

    vector<int> ans;
    int kk = k;

    for(int i = 0; i < n; i++){
        if(kk == 0) break;
        auto it = ss.lower_bound({events[i].sc, 0, 0, 0});
        if(it == ss.end() || (*it)[1] > events[i].f) continue;
        auto [r, l, st, cnt] = *it;
        int a = count(st, events[i].f);
        int b = count(succ[i], r);
        if(a+b+sum-cnt+1 < kk) continue;
        ans.pb(i);
        sum-=cnt;
        sum+=a+b;
        ss.erase(it);
        ss.insert({events[i].f, l, st, a});
        ss.insert({r, events[i].sc, succ[i], b});
        kk--;
    }

    if(ans.size() != k) cout << "-1\n", exit(0);
    for(int x: ans) cout << x+1 << "\n";
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:85:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |     if(ans.size() != k) cout << "-1\n", exit(0);
      |        ~~~~~~~~~~~^~~~

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