#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 17) ;
bool flag1, us[N + 1] ;
int n, cnt, k, a[N + 1], b[N + 1], dp[N + 1], pw[N + 1], mx[N + 1][18] ;
pair<pair<int, int>, int> p[N + 1] ;
vector<int> ans ;
map<int, int> mp ;
set<int> s ;
bool flag = 0 ;
vector<int> now, v[N + 1] ;
void dfs(int city, int last)
{
us[city] = 1 ;
now.push_back(city) ;
for(int i : v[city])
{
if(i == last)
continue ;
dfs(i, city) ;
}
}
void build_sparce_table()
{
for(int i = 2 ; i <= n ; i++)
pw[i] = pw[i / 2] + 1 ;
for(int i = 1 ; i <= n ; i++)
mx[i][0] = a[i] ;
for(int i = 1 ; i < 18 ; i++)
for(int j = 1 ; j <= n - (1 << i) + 1 ; j++)
mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1)) + 1][i - 1]) ;
}
int get_max(int l, int r)
{
int num = pw[r - l + 1] ;
return max(mx[l][num], mx[r - (1 << num) + 1][num]) ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n >> k ;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i] >> b[i] ;
if(a[i - 1] > a[i])
flag1 = 1 ;
p[i] = {{b[i], a[i]}, i} ;
s.insert(a[i]) ;
s.insert(b[i]) ;
}
// cout<<flag1<<'\n' ;
if(!flag1)
{
build_sparce_table() ;
for(int i = 1 ; i <= n ; i++)
{
int l = i, r = n + 1 ;
while(l + 1 < r)
{
int mid = (l + r) >> 1 ;
if(get_max(i + 1, mid) >= b[i])
r = mid ;
else
l = mid ;
}
if(r < n + 1)
v[i].push_back(r) ;
}
for(int i = 1 ; i <= n ; i++)
{
if(us[i])
continue ;
now.clear() ;
dfs(i, 1) ;
if(now.size() >= k)
{
for(int i = 0 ; i < k ; i++)
cout << now[i] << '\n' ;
return 0 ;
}
}
cout << "-1\n" ;
return 0 ;
}
// for(int i : s)
// {
// cnt++ ;
// mp[i] = cnt ;
// }
// sort(p + 1, p + n + 1) ;
// for(int i = 1 ; i <= n ; i++)
// {
// p[i].fi.se = mp[p[i].fi.se] ;
// p[i].fi.fi = mp[p[i].fi.fi] ;
// }
// for(int i = 1 ; i <= n ; i++)
// {
// dp[i] = 1 ;
// for(int j = 1 ; j < i ; j++)
// if(p[j].fi.fi <= p[i].fi.se)
// dp[i] = max(dp[j] + 1, dp[i]) ;
// }
// for(int i = 1 ; i <= n ; i++)
// {
// if(dp[i] < k)
// continue ;
// int cnt = dp[i] ;
// }
// cout << ans.size() << '\n' ;
// for(int i : ans)
// cout << i << '\n' ;
return 0 ;
}
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:80:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
80 | if(now.size() >= k)
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
32800 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3412 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3412 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 4 |
Incorrect |
65 ms |
32800 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
