Submission #529927

#	Time	Username	Problem	Language	Result	Execution time	Memory
529927		ajpiano	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	86 ms	14996 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 1e5+5;
const int lg = 18;

const int inf  = 1e9+5;

int blift[large][lg];

vector<pi> range;

int banc(int start, int eval){
    int ans = 0;
    for(int i = lg-1; i >= 0; i--){
        int x = blift[start][i];
        if(range[x].s <= eval){
            ans += 1<<i; start = x;
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k; cin >> n >> k;
    range.resize(n+2);
    vector<pi> lsort, rsort;
    for(int i = 1; i <= n; i++){
        int l,r; cin >> l >> r;
        range[i].f = l, range[i].s = r;
        lsort.push_back({l,i});
        rsort.push_back({r,i});
    }
    range[n+1] = {inf, inf+5};
    range[0] = {-1, 0};
    sort(lsort.begin(), lsort.end(), greater<pi>());
    sort(rsort.begin(), rsort.end(), greater<pi>());
    pi best = {inf, n+1};
    int ptr = 0;
    for(auto &a: rsort){
        for(; ptr < n && lsort[ptr].f >= a.f; ptr++){
            int i = lsort[ptr].s;
            best = min(best, {range[i].s,i});
        }
        blift[a.s][0] = best.s;
    }
    blift[0][0] = best.s;
    blift[n+1][0] = n+1;
    for(int i = 1; i < lg; i++)
        for(int j = 0; j <= n+1; j++)
            blift[j][i] = blift[blift[j][i-1]][i-1];
    set<pi> cur; //l, i
    int csz = 0;
    int cmax = banc(0, inf);
    vector<int> ans;
    cur.insert({range[0].f, 0});
    cur.insert({range[n+1].f, n+1});

    for(int i = 1; i <= n && csz < k; i++){
        //check for fit
        auto it = cur.lower_bound({range[i].f,-1});
        int indr = it->s;
        int indl = prev(it)->s;
        if(range[indl].s > range[i].f || range[indr].f < range[i].s) continue;

        //check to make sure at least k
        int pre = banc(indl, range[indr].f);
        int ne = banc(indl, range[i].f)+1+banc(i, range[indr].f);
        if(cmax+ne-pre < k) continue;
        cmax += ne-pre;
        cur.insert({range[i].f,i});
        ans.push_back(i);
        csz++;
    }
    if(ans.empty()) cout << "-1\n";
    else{
        assert(ans.size() == k);
        for(auto &a: ans) cout << a << "\n";
    }
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from event2.cpp:1:
event2.cpp: In function 'int main()':
event2.cpp:86:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         assert(ans.size() == k);
      |                ~~~~~~~~~~~^~~~

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