Submission #601280

#	Time	Username	Problem	Language	Result	Execution time	Memory
601280		lordlorinc	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	254 ms	22156 KiB

event2

#include <bits/stdc++.h>

using namespace std;

vector<pair<pair<int, int>, int> > sor, sor2;
vector<vector<int> > tabla;

set<pair<pair<int, int>, int> > ck;

int maxDb(int l, int r){
    
    int pos = lower_bound(sor.begin(), sor.end(), make_pair(make_pair(l, 1000000003), -1)) - sor.begin() - 1;
    
    int res = 0;
    for (int i = tabla[0].size() - 1; i >= 0; i--){
        if (tabla[pos][i] == -1) continue;
        if (sor[tabla[pos][i]].first.first <= r){
            pos = tabla[pos][i];
            res += (1 << i);
        }
    }
    // cout << l << " " << r << " " << res << endl;
    return res;
}

int main(){

    int n, m;
    cin >> n >> m;

    sor.resize(n + 2);

    for (int i = 0; i < n; i++){
        cin >> sor[i].first.second >> sor[i].first.first;
        sor[i].second = i + 1;
    }
    sor[n] = make_pair(make_pair(0, -1), 0);
    sor[n + 1] = make_pair(make_pair(1e9+2, 1e9+1), n + 1);
    n += 2;
    tabla.assign(n, vector<int>(log2(n + 1) + 1, -1));

    sor2 = sor;
    sort(sor.begin(), sor.end());
    int ind = 0;
    for (int i = 0; i < n; i++){
        
        while (ind < i && sor[ind].first.first <= sor[i].first.second){
            tabla[ind][0] = i;
            ind++;
        }
        // cout << i << " " << ind << endl;
        // cout << sor[i].first.first << " " << sor[i].first.second << " " << sor[i].second << endl;
    }

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

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

    ck.insert(make_pair(make_pair(0, -1), 0));
    ck.insert(make_pair(make_pair(1e9+2, 1e9+1), n + 1));
    int db = maxDb(0, 1e9);

    if (db < m){
        cout << -1 << endl;
        return 0;
    }

    // cout << db << endl;

    for (int i = 0; i < n - 2; i++){
        // if (ck.size() == m + 2) break;
        auto pos = ck.upper_bound(make_pair(make_pair(sor2[i].first.first, -2), -1));
        if (pos -> first.second < sor2[i].first.first){
            continue;
        }
        int r = pos -> first.second;
        pos--;
        if (pos -> first.first > sor2[i].first.second){
            continue;
        }
        int l = pos -> first.first;
        // cout << i << ": " << l << " " << r << endl;
        // cout << maxDb(l, r) << " " << maxDb(l, sor[i].first.second) << " " << maxDb(sor[i].first.first, r) << endl;
        if (db - maxDb(l, r) + maxDb(l, sor2[i].first.second) + maxDb(sor2[i].first.first, r) + 1 >= m){
            db = db - maxDb(l, r) + maxDb(l, sor2[i].first.second) + maxDb(sor2[i].first.first, r) + 1;
            ck.insert(sor2[i]);
        }
    }

    vector<int> mo;
    for (auto x : ck){
        mo.push_back(x.second);
    }

    sort(mo.begin(), mo.end());
    for (int i = 1; i <= m; i++){
        cout << mo[i] << '\n';
    }

    return 0;
}

/*

5 4
1 3
2 5
8 9
6 8
10 15
*/

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 1; i < tabla[0].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~

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