This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++){
| ~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |