#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int N, K, L[500005], R[500005], A[500005], ft2[500005], ft3[500005], occ[500005];
bool rec, inS[500005];
vector<int> ans, v;
set<ii> cfm;
multiset<ii> ft[500005];
set<iii> S;
vector<iii> tmp;
bool intersect(int a, int b, int c, int d) {
if (a > c) swap(a, c), swap(b, d);
return b > c;
}
inline int ls(int x) { return x & -x; }
ii qry(int p) {
ii ret = mp(LLONG_MAX, LLONG_MAX);
for (; p <= 2 * N; p += ls(p))
if (!ft[p].empty()) ret = min(ret, *ft[p].begin());
return ret;
}
void potadd(int x) {
occ[x]++;
for (int p = L[x]; p; p -= ls(p))
ft[p].emplace(R[x], x);
}
void potdel(int x) {
occ[x]--;
assert(occ[x] >= 0);
for (int p = L[x]; p; p -= ls(p)) {
assert(ft[p].find(mp(R[x], x)) != ft[p].end());
ft[p].erase(ft[p].find(mp(R[x], x)));
}
}
int ft2_qry(int p) {
int r = 0;
for (; p; p -= ls(p)) r += ft2[p];
return r;
}
void ft2_upd(int p, int v) {
for (; p <= 2 * N; p += ls(p)) ft2[p] += v;
}
int ft3_qry(int p) {
p = 2 * N - p + 1;
int r = 0;
for (; p; p -= ls(p)) r += ft3[p];
return r;
}
void ft3_upd(int p, int v) {
p = 2 * N - p + 1;
for (; p <= 2 * N; p += ls(p)) ft3[p] += v;
}
void addseg(int x) {
int lim;
auto it = S.lower_bound(mt(R[x], 0ll, 0ll));
if (it == S.end()) lim = LLONG_MAX;
else lim = g0(*it);
vector<set<iii>::iterator> todel;
while (it != S.begin()) {
--it;
if (intersect(g0(*it), g1(*it), L[x], R[x])) {
ft2_upd(g1(*it), -1);
ft3_upd(g0(*it), -1);
potadd(g2(*it));
todel.pb(it);
} else break;
}
for (auto i : todel) {
assert(inS[g2(*i)]);
inS[g2(*i)] = 0;
S.erase(i);
}
ft2_upd(R[x], 1);
ft3_upd(L[x], 1);
S.emplace(L[x], R[x], x);
assert(!inS[x]);
inS[x] = 1;
potdel(x);
auto tmp = qry(R[x]);
if (tmp.second != LLONG_MAX && tmp.first <= lim) {
assert(!rec);
rec = 1;
addseg(tmp.second);
rec = 0;
}
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i = 1; i <= N; i++) cin >> L[i] >> R[i], v.pb(L[i]), v.pb(R[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= N; i++) {
L[i] = lower_bound(v.begin(), v.end(), L[i]) - v.begin() + 1;
R[i] = lower_bound(v.begin(), v.end(), R[i]) - v.begin() + 1;
tmp.eb(R[i], L[i], i);
}
sort(tmp.begin(), tmp.end());
int lastr = LLONG_MIN;
for (int i = 1; i <= N; i++) potadd(i);
for (auto [r, l, i] : tmp)
if (lastr <= l) {
ft2_upd(R[i], 1);
ft3_upd(L[i], 1);
inS[i] = 1;
S.emplace(l, r, i);
potdel(i);
lastr = r;
}
int top = S.size();
if (S.size() < K) return cout << "-1\n", 0;
for (int i = 1; i <= N; i++) {
auto it = cfm.lower_bound(mp(R[i], 0ll));
bool yep = 1;
if (it != cfm.begin()) {
--it;
if (intersect(it->first, it->second, L[i], R[i])) yep = 0;
}
if (!yep) {
for (int j = 1; j <= N; j++)
if (inS[j]) assert(occ[j] == 0);
else assert(occ[j] == 1);
continue;
}
A[i] = ft2_qry(L[i]) + ft3_qry(R[i]) + 1;
auto tmp = qry(R[i]);
auto it2 = S.lower_bound(mt(R[i], 0ll, 0ll));
if (tmp.second != LLONG_MAX && (it2 == S.end() || tmp.first <= g0(*it2))) A[i]++;
assert(A[i] <= top);
if (A[i] >= K) {
cfm.emplace(L[i], R[i]);
ans.pb(i);
addseg(i);
}
for (int j : ans) assert(cfm.find(mp(L[j], R[j])) != cfm.end());
for (int j = 1; j <= N; j++)
if (inS[j]) assert(occ[j] == 0);
else assert(occ[j] == 1);
}
assert(ans.size() >= K);
for (int i = 0; i < K; i++) cout << ans[i] << '\n';
}
Compilation message
event2.cpp:122:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
122 | main() {
| ^~~~
event2.cpp: In function 'int main()':
event2.cpp:147:15: warning: comparison of integer expressions of different signedness: 'std::set<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
147 | if (S.size() < K) return cout << "-1\n", 0;
| ~~~~~~~~~^~~
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from event2.cpp:2:
event2.cpp:176:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
176 | assert(ans.size() >= K);
| ~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23852 KB |
Output is correct |
2 |
Correct |
15 ms |
23756 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Execution timed out |
3104 ms |
87028 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23848 KB |
Output is correct |
2 |
Correct |
15 ms |
23752 KB |
Output is correct |
3 |
Correct |
16 ms |
23816 KB |
Output is correct |
4 |
Correct |
16 ms |
23764 KB |
Output is correct |
5 |
Correct |
16 ms |
23824 KB |
Output is correct |
6 |
Correct |
20 ms |
23948 KB |
Output is correct |
7 |
Correct |
16 ms |
23756 KB |
Output is correct |
8 |
Correct |
16 ms |
23772 KB |
Output is correct |
9 |
Correct |
16 ms |
23756 KB |
Output is correct |
10 |
Correct |
15 ms |
23836 KB |
Output is correct |
11 |
Correct |
15 ms |
23840 KB |
Output is correct |
12 |
Correct |
15 ms |
23752 KB |
Output is correct |
13 |
Correct |
16 ms |
23788 KB |
Output is correct |
14 |
Correct |
15 ms |
23768 KB |
Output is correct |
15 |
Correct |
16 ms |
23828 KB |
Output is correct |
16 |
Correct |
16 ms |
23820 KB |
Output is correct |
17 |
Correct |
16 ms |
23756 KB |
Output is correct |
18 |
Correct |
16 ms |
23756 KB |
Output is correct |
19 |
Correct |
16 ms |
23756 KB |
Output is correct |
20 |
Correct |
16 ms |
23816 KB |
Output is correct |
21 |
Correct |
15 ms |
23860 KB |
Output is correct |
22 |
Correct |
16 ms |
23780 KB |
Output is correct |
23 |
Correct |
15 ms |
23756 KB |
Output is correct |
24 |
Correct |
15 ms |
23852 KB |
Output is correct |
25 |
Correct |
16 ms |
23832 KB |
Output is correct |
26 |
Correct |
15 ms |
23756 KB |
Output is correct |
27 |
Correct |
15 ms |
23756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23848 KB |
Output is correct |
2 |
Correct |
15 ms |
23752 KB |
Output is correct |
3 |
Correct |
16 ms |
23816 KB |
Output is correct |
4 |
Correct |
16 ms |
23764 KB |
Output is correct |
5 |
Correct |
16 ms |
23824 KB |
Output is correct |
6 |
Correct |
20 ms |
23948 KB |
Output is correct |
7 |
Correct |
16 ms |
23756 KB |
Output is correct |
8 |
Correct |
16 ms |
23772 KB |
Output is correct |
9 |
Correct |
16 ms |
23756 KB |
Output is correct |
10 |
Correct |
15 ms |
23836 KB |
Output is correct |
11 |
Correct |
15 ms |
23840 KB |
Output is correct |
12 |
Correct |
15 ms |
23752 KB |
Output is correct |
13 |
Correct |
16 ms |
23788 KB |
Output is correct |
14 |
Correct |
15 ms |
23768 KB |
Output is correct |
15 |
Correct |
16 ms |
23828 KB |
Output is correct |
16 |
Correct |
16 ms |
23820 KB |
Output is correct |
17 |
Correct |
16 ms |
23756 KB |
Output is correct |
18 |
Correct |
16 ms |
23756 KB |
Output is correct |
19 |
Correct |
16 ms |
23756 KB |
Output is correct |
20 |
Correct |
16 ms |
23816 KB |
Output is correct |
21 |
Correct |
15 ms |
23860 KB |
Output is correct |
22 |
Correct |
16 ms |
23780 KB |
Output is correct |
23 |
Correct |
15 ms |
23756 KB |
Output is correct |
24 |
Correct |
15 ms |
23852 KB |
Output is correct |
25 |
Correct |
16 ms |
23832 KB |
Output is correct |
26 |
Correct |
15 ms |
23756 KB |
Output is correct |
27 |
Correct |
15 ms |
23756 KB |
Output is correct |
28 |
Correct |
37 ms |
25252 KB |
Output is correct |
29 |
Correct |
36 ms |
25232 KB |
Output is correct |
30 |
Correct |
36 ms |
25220 KB |
Output is correct |
31 |
Correct |
35 ms |
25240 KB |
Output is correct |
32 |
Correct |
34 ms |
25220 KB |
Output is correct |
33 |
Correct |
21 ms |
25164 KB |
Output is correct |
34 |
Correct |
21 ms |
25136 KB |
Output is correct |
35 |
Correct |
481 ms |
25376 KB |
Output is correct |
36 |
Correct |
461 ms |
25548 KB |
Output is correct |
37 |
Correct |
326 ms |
25412 KB |
Output is correct |
38 |
Correct |
27 ms |
25264 KB |
Output is correct |
39 |
Correct |
333 ms |
25496 KB |
Output is correct |
40 |
Correct |
328 ms |
25292 KB |
Output is correct |
41 |
Correct |
332 ms |
25532 KB |
Output is correct |
42 |
Correct |
23 ms |
25292 KB |
Output is correct |
43 |
Incorrect |
85 ms |
25304 KB |
Output isn't correct |
44 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23852 KB |
Output is correct |
2 |
Correct |
15 ms |
23756 KB |
Output is correct |
3 |
Correct |
15 ms |
23752 KB |
Output is correct |
4 |
Execution timed out |
3104 ms |
87028 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |