#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 2e9;
int n, k;
int l[MAXN];
int r[MAXN];
int perm[MAXN];
std::vector <int> sol;
std::vector <int> ans;
std::vector <int> remaining;
bool intersecting(int x, int y)
{
return std::max(l[x], l[y]) < std::min(r[x], r[y]);
}
std::pair <int,int> canAdd(int idx)
{
int cntLeft = sol.size();
for (const int &i : ans)
{
if (intersecting(idx, i))
{
return {-1, -1};
}
}
int maxPopped = 0;
int minPopped = INF;
for (const int &i : sol)
{
if (intersecting(idx, i))
{
// std::cout << "pop: " << l[i] << ' ' << r[i] << '\n';
maxPopped = std::max(maxPopped, r[i]);
minPopped = std::min(minPopped, l[i]);
cntLeft--;
}
}
int allowedTo = INF;
int allowedFrom = 0;
for (const int &i : sol)
{
if (l[i] >= maxPopped)
{
allowedTo = std::min(allowedTo, l[i]);
}
if (r[i] <= minPopped)
{
allowedFrom = std::max(allowedFrom, r[i]);
}
}
int coolIdx = 0;
int coolIdx2 = 0;
for (const int &i : remaining)
{
if (r[i] <= allowedTo && l[i] >= r[idx])
{
// std::cout << coolUIDx
if (coolIdx == 0 || (r[i] < r[coolIdx]) || (r[i] == r[coolIdx] && l[i] > l[coolIdx]))
{
coolIdx = i;
}
}
if (l[i] >= allowedFrom && r[i] <= l[idx])
{
if (coolIdx2 == 0 || (r[i] < r[coolIdx2]) || (r[i] == r[coolIdx2] && l[i] > l[coolIdx2]))
{
// std::cout << "add: " << l[i] << ' ' << r[i] << ' ' << allowedFrom << ' ' << l[idx] << '\n';
coolIdx2 = i;
}
}
}
if ((coolIdx != 0) + (coolIdx2 != 0) - (coolIdx != 0 && coolIdx == coolIdx2) + cntLeft + ans.size() + 1 >= k)
{
return {coolIdx, coolIdx2};
} else
{
return {-1, -1};
}
}
void removeIntersecting(int idx)
{
std::vector <int> sol2;
for (const int &i : sol)
{
if (!intersecting(idx, i))
{
sol2.push_back(i);
}
}
sol = sol2;
std::vector <int> rem2;
for (const int &i : remaining)
{
if (!intersecting(idx, i))
{
rem2.push_back(i);
}
}
remaining = rem2;
}
void solve()
{
std::vector <std::pair <int, std::pair <int,bool>>> v;
for (int i = 1 ; i <= n ; ++i)
{
v.push_back({l[i], {i, false}});
v.push_back({r[i], {i, true}});
}
int cnt = 0;
int last = 0;
std::sort(v.begin(), v.end());
for (int i = 0 ; i < 2 * n ; ++i)
{
cnt += (v[i].first > last);
last = v[i].first;
if (v[i].second.second) r[v[i].second.first] = cnt;
else l[v[i].second.first] = cnt;
}
// std::cout << n << ' ' << k << '\n';
// for (int i = 1 ; i <= n ; ++i)
// {
// std::cout << l[i] << ' ' << r[i] << '\n';
// }
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
{
return r[x] < r[y] || (r[x] == r[y] && l[x] > l[y]);
});
for (int i = 1 ; i <= n ; ++i)
{
if (sol.empty() || !intersecting(sol.back(), perm[i]))
{
sol.push_back(perm[i]);
} else
{
remaining.push_back(perm[i]);
}
}
if (sol.size() < k)
{
std::cout << -1 << '\n';
return;
}
// std::cout << "sol is\n";
// for (const int &idx : sol)
// {
// std::cout << idx << ' ' << l[idx] << ' ' << r[idx] << '\n';
// }
for (int i = 1 ; i <= n && ans.size() < k ; ++i)
{
auto [res, second] = canAdd(i);
// std::cout << "res: " << res << ' ' << second << '\n';
if (res != -1)
{
ans.push_back(i);
removeIntersecting(i);
if (res != 0)
{
// std::cout << " bonus: " << i << ' ' << res << '\n';
sol.push_back(res);
for (int &i : remaining)
{
if (i == res)
{
std::swap(i, remaining.back());
remaining.pop_back();
break;
}
}
}
if (second != 0)
{
// std::cout << " bonus: " << i << ' ' << res << '\n';
sol.push_back(second);
for (int &i : remaining)
{
if (i == second)
{
std::swap(i, remaining.back());
remaining.pop_back();
break;
}
}
}
}
}
for (const int &idx : ans)
{
std::cout << idx << '\n';
}
}
void input()
{
std::cin >> n >> k;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> l[i] >> r[i];
// l[i]++;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
event2.cpp: In function 'std::pair<int, int> canAdd(int)':
event2.cpp:91:110: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
91 | if ((coolIdx != 0) + (coolIdx2 != 0) - (coolIdx != 0 && coolIdx == coolIdx2) + cntLeft + ans.size() + 1 >= k)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
event2.cpp: In function 'void solve()':
event2.cpp:169:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
169 | if (sol.size() < k)
| ~~~~~~~~~~~^~~
event2.cpp:181:43: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
181 | for (int i = 1 ; i <= n && ans.size() < k ; ++i)
| ~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
3015 ms |
5312 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
2 ms |
604 KB |
Output is correct |
29 |
Correct |
2 ms |
604 KB |
Output is correct |
30 |
Correct |
2 ms |
604 KB |
Output is correct |
31 |
Correct |
2 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
600 KB |
Output is correct |
33 |
Correct |
1 ms |
604 KB |
Output is correct |
34 |
Correct |
1 ms |
604 KB |
Output is correct |
35 |
Correct |
25 ms |
672 KB |
Output is correct |
36 |
Correct |
24 ms |
604 KB |
Output is correct |
37 |
Correct |
17 ms |
600 KB |
Output is correct |
38 |
Correct |
1 ms |
604 KB |
Output is correct |
39 |
Correct |
26 ms |
600 KB |
Output is correct |
40 |
Correct |
21 ms |
604 KB |
Output is correct |
41 |
Correct |
18 ms |
604 KB |
Output is correct |
42 |
Correct |
2 ms |
604 KB |
Output is correct |
43 |
Incorrect |
8 ms |
604 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
3015 ms |
5312 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |