#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <optional>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define int ll
struct range {
ll l, r;
};
struct event {
int id;
::range range;
event() : id(-1), range{ -1, -1 } {}
event(int id, ::range range) : id(id), range(range) {}
};
struct started_range {
ll r;
event start;
::range range() const {
return { start.range.r, r };
}
explicit started_range(ll r) : r(r), start(-1, ::range{ -INT_MAX, -INT_MAX }) {}
started_range(ll r, const event& start) : r(r), start(start) {}
bool operator <(const started_range& other) const {
return r < other.r;
}
};
int sqrt_n;
vector<event> events;
event first;
vector<optional<event>> next_one;
vector<optional<event>> next_sqrt_n;
int max_events(const started_range& sr) {
ll r = sr.r;
const int after_id = sr.start.id;
int ans = 0;
int cur = after_id;
if (cur == -1) {
ans++;
cur = first.id;
}
while (next_sqrt_n[cur] && next_sqrt_n[cur]->range.r <= r) {
ans += sqrt_n;
cur = next_sqrt_n[cur]->id;
}
while (next_one[cur] && next_one[cur]->range.r <= r) {
ans++;
cur = next_one[cur]->id;
}
return ans;
}
signed main() {
int n, k;
cin >> n >> k;
events.resize(n);
for (int i = 0; i < n; i++) {
event& e = events[i];
e.id = i;
cin >> e.range.l >> e.range.r;
}
next_one.resize(n);
{
vector<event> l_rev_sorted = events;
sort(l_rev_sorted.begin(), l_rev_sorted.end(), [](const event& a, const event& b) {
return a.range.l > b.range.l;
});
vector<event> r_rev_sorted = events;
sort(r_rev_sorted.begin(), r_rev_sorted.end(), [](const event& a, const event& b) {
return a.range.r > b.range.r;
});
int r_min = -1;
int l_idx = 0;
for (const event& cur : r_rev_sorted) {
while (l_idx < l_rev_sorted.size()
&& l_rev_sorted[l_idx].range.l >= cur.range.r) {
if (r_min == - 1 || l_rev_sorted[l_idx].range.r < events[r_min].range.r)
r_min = l_rev_sorted[l_idx].id;
l_idx++;
}
if (r_min != -1)
next_one[cur.id] = events[r_min];
}
first = r_rev_sorted.back();
}
// does not need to be exact
sqrt_n = int(sqrt(double(n)));
next_sqrt_n.resize(n);
for (int i = 0; i < n; i++) {
int cur = i;
for (int j = 0; j < sqrt_n && cur != -1; j++) {
if (next_one[cur])
cur = next_one[cur]->id;
else
cur = -1;
}
if (cur != -1)
next_sqrt_n[i] = events[cur];
}
set<started_range> usable = { started_range(INT_MAX) };
int cur_events = max_events(*usable.begin());
if (cur_events < k) {
cout << "-1\n";
return 0;
}
vector<bool> in(n, false);
for (const auto& tested : events) {
auto usable_it = usable.lower_bound(started_range(tested.range.r));
if (usable_it->range().l > tested.range.l)
continue;
int before_split = max_events(*usable_it);
started_range split_l = *usable_it;
split_l.r = tested.range.l;
started_range split_r{ usable_it->r, tested };
int after_split = max_events(split_l) + 1 + max_events(split_r);
if (cur_events - before_split + after_split >= k) {
in[tested.id] = true;
usable.erase(*usable_it);
usable.insert(split_l);
usable.insert(split_r);
}
}
vector<int> solution;
for (int i = 0; solution.size() < k; i++)
if (in[i])
solution.push_back(i);
for (const int x : solution)
cout << x + 1 << "\n";
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:104:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while (l_idx < l_rev_sorted.size()
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
event2.cpp:175:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
175 | for (int i = 0; solution.size() < k; i++)
| ~~~~~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
479 ms |
20436 KB |
Output is correct |
5 |
Correct |
476 ms |
20356 KB |
Output is correct |
6 |
Correct |
475 ms |
20288 KB |
Output is correct |
7 |
Correct |
480 ms |
20064 KB |
Output is correct |
8 |
Correct |
479 ms |
20320 KB |
Output is correct |
9 |
Correct |
460 ms |
20340 KB |
Output is correct |
10 |
Correct |
481 ms |
20196 KB |
Output is correct |
11 |
Correct |
455 ms |
20336 KB |
Output is correct |
12 |
Correct |
321 ms |
16652 KB |
Output is correct |
13 |
Correct |
303 ms |
16596 KB |
Output is correct |
14 |
Correct |
324 ms |
16508 KB |
Output is correct |
15 |
Correct |
318 ms |
16512 KB |
Output is correct |
16 |
Correct |
260 ms |
12352 KB |
Output is correct |
17 |
Correct |
257 ms |
12356 KB |
Output is correct |
18 |
Correct |
257 ms |
12504 KB |
Output is correct |
19 |
Correct |
223 ms |
12356 KB |
Output is correct |
20 |
Incorrect |
222 ms |
12400 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
479 ms |
20436 KB |
Output is correct |
5 |
Correct |
476 ms |
20356 KB |
Output is correct |
6 |
Correct |
475 ms |
20288 KB |
Output is correct |
7 |
Correct |
480 ms |
20064 KB |
Output is correct |
8 |
Correct |
479 ms |
20320 KB |
Output is correct |
9 |
Correct |
460 ms |
20340 KB |
Output is correct |
10 |
Correct |
481 ms |
20196 KB |
Output is correct |
11 |
Correct |
455 ms |
20336 KB |
Output is correct |
12 |
Correct |
321 ms |
16652 KB |
Output is correct |
13 |
Correct |
303 ms |
16596 KB |
Output is correct |
14 |
Correct |
324 ms |
16508 KB |
Output is correct |
15 |
Correct |
318 ms |
16512 KB |
Output is correct |
16 |
Correct |
260 ms |
12352 KB |
Output is correct |
17 |
Correct |
257 ms |
12356 KB |
Output is correct |
18 |
Correct |
257 ms |
12504 KB |
Output is correct |
19 |
Correct |
223 ms |
12356 KB |
Output is correct |
20 |
Incorrect |
222 ms |
12400 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |