#include <bits/stdc++.h>
using namespace std;
const int MX=2e5+5;
int N,K;
int L[MX], R[MX], nxt[MX], deg[MX];
vector<pair<int,int>> ptL[MX], ptR[MX];
map<int,int> id;
vector<int> adj[MX];
int up[MX][20];
void dfs(int v) {
for(int k=1;k<20;k++) {
up[v][k]=up[up[v][k-1]][k-1];
}
for(auto u:adj[v]) {
up[u][0]=v;
dfs(u);
}
}
int calc(int l, int r) {
int v=nxt[l], res=0;
if(v==1e9) return 0;
if(R[v]>r) return 0;
for(int k=19;k>=0;k--) {
if(up[v][k]!=0 && R[up[v][k]]<=r) {
res+=1<<k;
v=up[v][k];
}
}
return res+1;
}
bool chk(pair<int,int> p, pair<int,int> q) {
if(p.second<=q.first) return false;
return true;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>K;
for(int i=1;i<=N;i++) {
cin>>L[i]>>R[i];
id[L[i]]=0;
id[R[i]]=0;
}
int z=0;
for(auto &[x,y]:id) {
y=++z;
}
for(int i=1;i<=N;i++) {
L[i]=id[L[i]];
R[i]=id[R[i]];
ptL[L[i]].push_back({R[i],i});
ptR[R[i]].push_back({L[i],i});
}
pair<int,int> lst={1e9,1e9};
for(int p=z;p>=1;p--) {
for(auto [r,id]:ptL[p]) {
lst=min(lst,make_pair(r,id));
}
nxt[p]=lst.second;
for(auto [l,id]:ptR[p]) {
if(lst.second!=1e9) {
adj[lst.second].push_back(id);
}
}
}
for(int i=1;i<=N;i++) {
for(auto j:adj[i]) deg[j]+=1;
}
for(int i=1;i<=N;i++) {
if(!deg[i]) {
dfs(i);
}
}
set<pair<int,int>> ranges;
vector<int> ans;
for(int i=1;i<=N;i++) {
int a=1,b=z;
auto it=ranges.lower_bound(make_pair(R[i],0));
if(it!=ranges.begin()) {
it--;
if(chk(*it,make_pair(L[i],R[i]))) continue; // intersected
a=it->second;
}
auto itt=ranges.lower_bound(make_pair(R[i],0));
if(itt!=ranges.end()) {
b=itt->first;
}
if(1+calc(a,L[i])+calc(R[i],b)+calc(1,a)+calc(b,z)>=K) {
assert(L[i]<=R[i]);
ranges.insert({L[i],R[i]});
ans.push_back(i);
}
if(ans.size()==K) break;
}
if(ans.size()<K) {
cout<<-1<<'\n';
return 0;
}
for(auto x:ans) {
cout<<x<<'\n';
}
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:111:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
111 | if(ans.size()==K) break;
| ~~~~~~~~~~^~~
event2.cpp:114:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
114 | if(ans.size()<K) {
| ~~~~~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16728 KB |
Output is correct |
3 |
Correct |
4 ms |
16728 KB |
Output is correct |
4 |
Correct |
126 ms |
53960 KB |
Output is correct |
5 |
Correct |
129 ms |
53580 KB |
Output is correct |
6 |
Correct |
118 ms |
53268 KB |
Output is correct |
7 |
Correct |
115 ms |
52940 KB |
Output is correct |
8 |
Correct |
122 ms |
53812 KB |
Output is correct |
9 |
Correct |
128 ms |
53628 KB |
Output is correct |
10 |
Correct |
118 ms |
53448 KB |
Output is correct |
11 |
Correct |
116 ms |
52916 KB |
Output is correct |
12 |
Correct |
115 ms |
49516 KB |
Output is correct |
13 |
Correct |
114 ms |
49108 KB |
Output is correct |
14 |
Correct |
105 ms |
48848 KB |
Output is correct |
15 |
Correct |
103 ms |
48588 KB |
Output is correct |
16 |
Correct |
105 ms |
44264 KB |
Output is correct |
17 |
Correct |
89 ms |
43856 KB |
Output is correct |
18 |
Correct |
89 ms |
43856 KB |
Output is correct |
19 |
Correct |
94 ms |
42324 KB |
Output is correct |
20 |
Incorrect |
96 ms |
42232 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
4 ms |
16728 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
16732 KB |
Output is correct |
8 |
Correct |
3 ms |
16732 KB |
Output is correct |
9 |
Correct |
4 ms |
16732 KB |
Output is correct |
10 |
Correct |
5 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16728 KB |
Output is correct |
12 |
Correct |
4 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
16732 KB |
Output is correct |
15 |
Correct |
3 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16832 KB |
Output is correct |
17 |
Correct |
3 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
16732 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
4 ms |
16732 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
4 ms |
16732 KB |
Output is correct |
25 |
Correct |
3 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
27 |
Correct |
3 ms |
16844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16732 KB |
Output is correct |
2 |
Correct |
4 ms |
16732 KB |
Output is correct |
3 |
Correct |
4 ms |
16728 KB |
Output is correct |
4 |
Correct |
3 ms |
16732 KB |
Output is correct |
5 |
Correct |
3 ms |
16732 KB |
Output is correct |
6 |
Correct |
4 ms |
16732 KB |
Output is correct |
7 |
Correct |
4 ms |
16732 KB |
Output is correct |
8 |
Correct |
3 ms |
16732 KB |
Output is correct |
9 |
Correct |
4 ms |
16732 KB |
Output is correct |
10 |
Correct |
5 ms |
16732 KB |
Output is correct |
11 |
Correct |
3 ms |
16728 KB |
Output is correct |
12 |
Correct |
4 ms |
16732 KB |
Output is correct |
13 |
Correct |
3 ms |
16732 KB |
Output is correct |
14 |
Correct |
3 ms |
16732 KB |
Output is correct |
15 |
Correct |
3 ms |
16732 KB |
Output is correct |
16 |
Correct |
3 ms |
16832 KB |
Output is correct |
17 |
Correct |
3 ms |
16732 KB |
Output is correct |
18 |
Correct |
4 ms |
16732 KB |
Output is correct |
19 |
Correct |
3 ms |
16732 KB |
Output is correct |
20 |
Correct |
4 ms |
16732 KB |
Output is correct |
21 |
Correct |
4 ms |
16732 KB |
Output is correct |
22 |
Correct |
4 ms |
16732 KB |
Output is correct |
23 |
Correct |
4 ms |
16732 KB |
Output is correct |
24 |
Correct |
4 ms |
16732 KB |
Output is correct |
25 |
Correct |
3 ms |
16732 KB |
Output is correct |
26 |
Correct |
4 ms |
16732 KB |
Output is correct |
27 |
Correct |
3 ms |
16844 KB |
Output is correct |
28 |
Correct |
7 ms |
19548 KB |
Output is correct |
29 |
Incorrect |
7 ms |
19548 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
16728 KB |
Output is correct |
2 |
Correct |
4 ms |
16728 KB |
Output is correct |
3 |
Correct |
4 ms |
16728 KB |
Output is correct |
4 |
Correct |
126 ms |
53960 KB |
Output is correct |
5 |
Correct |
129 ms |
53580 KB |
Output is correct |
6 |
Correct |
118 ms |
53268 KB |
Output is correct |
7 |
Correct |
115 ms |
52940 KB |
Output is correct |
8 |
Correct |
122 ms |
53812 KB |
Output is correct |
9 |
Correct |
128 ms |
53628 KB |
Output is correct |
10 |
Correct |
118 ms |
53448 KB |
Output is correct |
11 |
Correct |
116 ms |
52916 KB |
Output is correct |
12 |
Correct |
115 ms |
49516 KB |
Output is correct |
13 |
Correct |
114 ms |
49108 KB |
Output is correct |
14 |
Correct |
105 ms |
48848 KB |
Output is correct |
15 |
Correct |
103 ms |
48588 KB |
Output is correct |
16 |
Correct |
105 ms |
44264 KB |
Output is correct |
17 |
Correct |
89 ms |
43856 KB |
Output is correct |
18 |
Correct |
89 ms |
43856 KB |
Output is correct |
19 |
Correct |
94 ms |
42324 KB |
Output is correct |
20 |
Incorrect |
96 ms |
42232 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |