#include <bits/stdc++.h>
using namespace std;
const int MXN = 100001;
const int MXLG = 19;
int l[MXN], r[MXN];
int ljmp[MXN][MXLG], rjmp[MXN][MXLG];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int N, K; cin >> N >> K;
for(int i = 1; i <= N; i++) {
cin >> l[i] >> r[i];
}
{
map<int, vector<int>> eve;
for(int i = 1; i <= N; i++) eve[l[i]].push_back(i), eve[r[i]].push_back(-i);
multiset<pair<int, int>> rs;
for(int i = 1; i <= N; i++) rs.insert({r[i], i});
for(auto [u, v] : eve) {
for(int i : v) {
if(i < 0) {
rjmp[-i][0] = (rs.size() > 0) ? (*rs.begin()).second : 0;
}
}
for(int i : v) {
if(i > 0) {
rs.erase(rs.find({r[i], i}));
}
}
}
}
{
map<int, vector<int>> eve;
for(int i = 1; i <= N; i++) eve[-l[i]].push_back(-i), eve[-r[i]].push_back(i);
multiset<pair<int, int>> ls;
for(int i = 1; i <= N; i++) ls.insert({l[i], i});
for(auto [u, v] : eve) {
for(int i : v) {
if(i < 0) {
ljmp[-i][0] = (ls.size() > 0) ? (*ls.rbegin()).second : 0;
}
}
for(int i : v) {
if(i > 0) {
ls.erase(ls.find({l[i], i}));
}
}
}
}
for(int i = 0; i < MXLG - 1; i++) {
for(int j = 1; j <= N; j++) {
ljmp[j][i + 1] = ljmp[ljmp[j][i]][i];
rjmp[j][i + 1] = rjmp[rjmp[j][i]][i];
}
}
vector<int> ans;
set<pair<int, int>> ls, rs;
ls.insert({0, N});
rs.insert({0, N});
ls.insert({1e9+1, N});
rs.insert({1e9+1, N});
int curv = N;
for(int i = 1; i <= N; i++) {
auto [lb, pv1] = *prev(rs.upper_bound({r[i], N}));
auto [rb, pv2] = *ls.lower_bound({l[i], 0});
auto [firstr, _] = *rs.upper_bound({l[i], N});
auto [firstl, _2] = *ls.upper_bound({l[i], N});
if(l[i] < lb || rb < r[i] || firstr < firstl) {
continue;
}
int lv = 0, rv = 0;
int li = i, ri = i;
for(int j = MXLG - 1; j >= 0; j--) {
if(ljmp[li][j] != 0 && lb <= l[ljmp[li][j]]) {
li = ljmp[li][j];
lv += 1 << j;
}
if(rjmp[ri][j] != 0 && r[rjmp[ri][j]] < rb) {
ri = rjmp[ri][j];
rv += 1 << j;
}
}
if(curv - min(pv1, pv2) + lv + rv + 1 >= K) {
ans.push_back(i);
curv = curv - min(pv1, pv2) + lv + rv + 1;
ls.insert({l[i], lv});
rs.insert({r[i], rv});
}
if(ans.size() == K) break;
}
if(ans.size() == 0) cout << "-1\n";
else {
for(int i : ans) cout << i << "\n";
}
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
88 | if(ans.size() == K) break;
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
219 ms |
43172 KB |
Output is correct |
5 |
Correct |
220 ms |
45148 KB |
Output is correct |
6 |
Correct |
215 ms |
44888 KB |
Output is correct |
7 |
Correct |
209 ms |
44836 KB |
Output is correct |
8 |
Correct |
222 ms |
45144 KB |
Output is correct |
9 |
Correct |
231 ms |
45156 KB |
Output is correct |
10 |
Correct |
218 ms |
45136 KB |
Output is correct |
11 |
Correct |
213 ms |
45080 KB |
Output is correct |
12 |
Correct |
204 ms |
45060 KB |
Output is correct |
13 |
Correct |
204 ms |
44904 KB |
Output is correct |
14 |
Correct |
193 ms |
44880 KB |
Output is correct |
15 |
Correct |
185 ms |
44888 KB |
Output is correct |
16 |
Correct |
192 ms |
44888 KB |
Output is correct |
17 |
Correct |
187 ms |
44624 KB |
Output is correct |
18 |
Correct |
182 ms |
44640 KB |
Output is correct |
19 |
Correct |
185 ms |
44884 KB |
Output is correct |
20 |
Correct |
180 ms |
44500 KB |
Output is correct |
21 |
Correct |
180 ms |
44544 KB |
Output is correct |
22 |
Correct |
206 ms |
44636 KB |
Output is correct |
23 |
Correct |
200 ms |
44628 KB |
Output is correct |
24 |
Correct |
205 ms |
44632 KB |
Output is correct |
25 |
Correct |
203 ms |
44624 KB |
Output is correct |
26 |
Correct |
203 ms |
44580 KB |
Output is correct |
27 |
Correct |
212 ms |
44644 KB |
Output is correct |
28 |
Correct |
143 ms |
44624 KB |
Output is correct |
29 |
Correct |
141 ms |
44536 KB |
Output is correct |
30 |
Correct |
155 ms |
44628 KB |
Output is correct |
31 |
Correct |
169 ms |
45140 KB |
Output is correct |
32 |
Correct |
184 ms |
44624 KB |
Output is correct |
33 |
Correct |
206 ms |
44440 KB |
Output is correct |
34 |
Correct |
186 ms |
44632 KB |
Output is correct |
35 |
Correct |
169 ms |
44628 KB |
Output is correct |
36 |
Correct |
157 ms |
44624 KB |
Output is correct |
37 |
Correct |
208 ms |
44884 KB |
Output is correct |
38 |
Correct |
205 ms |
44896 KB |
Output is correct |
39 |
Correct |
205 ms |
44896 KB |
Output is correct |
40 |
Correct |
210 ms |
44892 KB |
Output is correct |
41 |
Correct |
197 ms |
44880 KB |
Output is correct |
42 |
Correct |
148 ms |
44624 KB |
Output is correct |
43 |
Correct |
197 ms |
44880 KB |
Output is correct |
44 |
Correct |
193 ms |
44892 KB |
Output is correct |
45 |
Correct |
194 ms |
44896 KB |
Output is correct |
46 |
Correct |
194 ms |
44892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2512 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2648 KB |
Output is correct |
5 |
Correct |
0 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2512 KB |
Output is correct |
13 |
Correct |
1 ms |
2396 KB |
Output is correct |
14 |
Correct |
1 ms |
2396 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
0 ms |
2396 KB |
Output is correct |
4 |
Correct |
219 ms |
43172 KB |
Output is correct |
5 |
Correct |
220 ms |
45148 KB |
Output is correct |
6 |
Correct |
215 ms |
44888 KB |
Output is correct |
7 |
Correct |
209 ms |
44836 KB |
Output is correct |
8 |
Correct |
222 ms |
45144 KB |
Output is correct |
9 |
Correct |
231 ms |
45156 KB |
Output is correct |
10 |
Correct |
218 ms |
45136 KB |
Output is correct |
11 |
Correct |
213 ms |
45080 KB |
Output is correct |
12 |
Correct |
204 ms |
45060 KB |
Output is correct |
13 |
Correct |
204 ms |
44904 KB |
Output is correct |
14 |
Correct |
193 ms |
44880 KB |
Output is correct |
15 |
Correct |
185 ms |
44888 KB |
Output is correct |
16 |
Correct |
192 ms |
44888 KB |
Output is correct |
17 |
Correct |
187 ms |
44624 KB |
Output is correct |
18 |
Correct |
182 ms |
44640 KB |
Output is correct |
19 |
Correct |
185 ms |
44884 KB |
Output is correct |
20 |
Correct |
180 ms |
44500 KB |
Output is correct |
21 |
Correct |
180 ms |
44544 KB |
Output is correct |
22 |
Correct |
206 ms |
44636 KB |
Output is correct |
23 |
Correct |
200 ms |
44628 KB |
Output is correct |
24 |
Correct |
205 ms |
44632 KB |
Output is correct |
25 |
Correct |
203 ms |
44624 KB |
Output is correct |
26 |
Correct |
203 ms |
44580 KB |
Output is correct |
27 |
Correct |
212 ms |
44644 KB |
Output is correct |
28 |
Correct |
143 ms |
44624 KB |
Output is correct |
29 |
Correct |
141 ms |
44536 KB |
Output is correct |
30 |
Correct |
155 ms |
44628 KB |
Output is correct |
31 |
Correct |
169 ms |
45140 KB |
Output is correct |
32 |
Correct |
184 ms |
44624 KB |
Output is correct |
33 |
Correct |
206 ms |
44440 KB |
Output is correct |
34 |
Correct |
186 ms |
44632 KB |
Output is correct |
35 |
Correct |
169 ms |
44628 KB |
Output is correct |
36 |
Correct |
157 ms |
44624 KB |
Output is correct |
37 |
Correct |
208 ms |
44884 KB |
Output is correct |
38 |
Correct |
205 ms |
44896 KB |
Output is correct |
39 |
Correct |
205 ms |
44896 KB |
Output is correct |
40 |
Correct |
210 ms |
44892 KB |
Output is correct |
41 |
Correct |
197 ms |
44880 KB |
Output is correct |
42 |
Correct |
148 ms |
44624 KB |
Output is correct |
43 |
Correct |
197 ms |
44880 KB |
Output is correct |
44 |
Correct |
193 ms |
44892 KB |
Output is correct |
45 |
Correct |
194 ms |
44896 KB |
Output is correct |
46 |
Correct |
194 ms |
44892 KB |
Output is correct |
47 |
Correct |
1 ms |
2396 KB |
Output is correct |
48 |
Correct |
0 ms |
2396 KB |
Output is correct |
49 |
Correct |
1 ms |
2396 KB |
Output is correct |
50 |
Correct |
1 ms |
2648 KB |
Output is correct |
51 |
Correct |
0 ms |
2396 KB |
Output is correct |
52 |
Correct |
1 ms |
2396 KB |
Output is correct |
53 |
Correct |
1 ms |
2396 KB |
Output is correct |
54 |
Correct |
1 ms |
2396 KB |
Output is correct |
55 |
Correct |
1 ms |
2396 KB |
Output is correct |
56 |
Correct |
1 ms |
2396 KB |
Output is correct |
57 |
Correct |
1 ms |
2396 KB |
Output is correct |
58 |
Correct |
1 ms |
2512 KB |
Output is correct |
59 |
Correct |
1 ms |
2396 KB |
Output is correct |
60 |
Correct |
1 ms |
2396 KB |
Output is correct |
61 |
Correct |
1 ms |
2396 KB |
Output is correct |
62 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
63 |
Halted |
0 ms |
0 KB |
- |