Submission #590143

#	Time	Username	Problem	Language	Result	Execution time	Memory
590143		lordlorinc	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	245 ms	23284 KiB

event2

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<pair<pair<int, int>, int> > sor, events;
vector<vector<int> > nexts;
set<pair<pair<int, int>, int> > inter;
vector<int> eventidTosorid, soridToeventid;

int count(int l, int r){
    std::set<std::pair<std::pair<int, int>, int>>::iterator pos = inter.upper_bound(make_pair(make_pair(r, -1), -1));
    pos--;
    int ind = pos -> second;
    // cout << ind << endl;
    int db = 1, i = 0, res = 0;
    while (true){
        if (nexts[ind][i] == -1) break;
        if (sor[nexts[ind][i]].first.first > r) break;
        i++;
        db <<= 1;
    }
    // cout << db << endl;
    while (i >= 0){
        if (nexts[ind][i] == -1){
            i--;
            db >>= 1;
            continue;
        }
        if (sor[nexts[ind][i]].first.first <= r){
            res += db;
            ind = nexts[ind][i];
        }
        i--;
        db >>= 1;
    }
    // cout << l << " " << r << " " << res << endl;
    return res;
}


int main(){

    cin >> n >> k;
    sor.resize(n);
    events.resize(n);
    for (int i = 0; i < n; i++){
        int a, b; 
        cin >> a >> b;
        sor[i] = make_pair(make_pair(b, a), i);
        events[i] = make_pair(make_pair(a, b), i);
    }
    sor.push_back(make_pair(make_pair(0, -1), n));
    sor.push_back(make_pair(make_pair(1e9 + 2, 1e9 + 1), n + 1));

    sort (sor.begin(), sor.end());


    eventidTosorid.assign(n + 2, 0);
    soridToeventid.assign(n + 2, 0);
    for (int i = 0; i < n + 2; i++){
        soridToeventid[i] = sor[i].second;
        eventidTosorid[sor[i].second] = i;
    }

    nexts.assign(n + 2, vector<int> (int(log2(n + 2)) + 2, -1));
    int l = 0;
    for (int i = 1; i < n + 2; i++){
        while (sor[l].first.first <= sor[i].first.second){
            nexts[l][0] = i;
            l++;
        }
    }
    // for (int i = 0; i < n + 2; i++){
    //     cout << sor[i].first.first << " " << sor[i].first.second << " " << sor[i].second << endl;
    // }
    // for (int i = 0; i < n + 2; i++){
    //     cout << nexts[i][0] << " ";
    // }
    // cout << endl;

    for (int i = 1; i < nexts[0].size(); i++){
        for (int j = 0; j < n + 2; j++){
            if (nexts[j][i - 1] == -1) continue;
            nexts[j][i] = nexts[nexts[j][i - 1]][i - 1];
        }
    }

    // for (int i = 0; i < n + 2; i++){
    //     cout << nexts[i][0] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < n + 2; i++){
    //     cout << nexts[i][1] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < n + 2; i++){
    //     cout << nexts[i][2] << " ";
    // }
    // cout << endl;
    // for (int i = 0; i < n + 2; i++){
    //     cout << nexts[i][2] << " ";
    // }
    // cout << endl;
    // cout << nexts[0].size() << endl;

    inter.insert(make_pair(make_pair(-1, 0), eventidTosorid[n]));
    inter.insert(make_pair(make_pair(1e9 + 1, 1e9 + 2), eventidTosorid[n + 1]));

    int db = count(0, 1e9);
    // cout << "db: " << db << endl;
    if (db < k){
        cout << -1 << endl;
        return 0;
    }

    for (int i = 0; i < n; i++){
        std::set<std::pair<std::pair<int, int>, int>>::iterator it = inter.upper_bound(make_pair(make_pair(events[i].first.second, -1), -1));
        int nextPos = it -> second;
        it--;
        int prevPos = it -> second;
        if (sor[prevPos].first.first > events[i].first.first) continue;
        // cout << "IND: " << i << endl;
        int a = count(sor[prevPos].first.first, sor[nextPos].first.second);
            inter.insert(make_pair(events[i].first, eventidTosorid[i]));
        int b = count(sor[prevPos].first.first, events[i].first.first);
        int c = count (events[i].first.second, sor[nextPos].first.second);
        if (db - a + b + c + 1 >= k){
            db = db - a + b + c + 1;
        }
        else inter.erase(make_pair(events[i].first, eventidTosorid[i]));
        if (inter.size() == k + 2) break;
    }

    vector<int> mo;
    for (auto x : inter){
        if (soridToeventid[x.second] < n){
            mo.push_back(soridToeventid[x.second]);
        }
    }
    sort(mo.begin(), mo.end());
    for (int x : mo) cout << x + 1 << "\n";

    return 0;
}

/*

4 3
1 4
3 5
4 9
7 10

*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for (int i = 1; i < nexts[0].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~
event2.cpp:132:26: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |         if (inter.size() == k + 2) break;
      |             ~~~~~~~~~~~~~^~~~~~~~

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