이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define INF 1000000009
int n, k, m;
array<int, 2> arr[MAXN];
vector<array<int, 2>> tmp;
vector<array<int, 2>> good;
set<array<int, 2>> st;
int dp[MAXN];
int fa[MAXN][20];
bool cmp(array<int, 2> a, array<int, 2> b){
if(a[1] != b[1]) return a[1] < b[1];
return a[0] < b[0];
}
int get(int l, int r){
int p = lower_bound(good.begin(), good.end(), array<int, 2>{r, r}, cmp)-good.begin()-1;
if(good[p][0] < l) return 0;
int res = dp[p];
// cout << res << endl;
for(int i = 19; i>=0; i--){
if(good[fa[p][i]][0] >= l) p = fa[p][i];
}
p = lower_bound(good.begin(), good.end(), array<int, 2>{good[p][0], good[p][0]}, cmp)-good.begin()-1;
return res - dp[p];
}
int main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
tmp.resize(n);
for(int i = 0; i<n; i++){
cin >> arr[i][0] >> arr[i][1];
tmp[i] = arr[i];
}
sort(tmp.begin(), tmp.end(), [&](array<int, 2> a, array<int, 2> b){
return a[1]-a[0] < b[1]-b[0];
});
for(auto p : tmp){
auto it = st.lower_bound(p);
if(it != st.end() && (*it)[1] <= p[1]) continue;
good.push_back(p);
}
sort(good.begin(), good.end());
m = good.size();
good.insert(good.begin(), {-1, -1});
for(int i = 1; i<=m; i++){
int pos = lower_bound(good.begin(), good.end(), array<int,2>{good[i][0], good[i][0]}, cmp)-good.begin()-1;
dp[i] = 1+dp[pos];
fa[i][0] = pos;
for(int j = 1; j<20; j++) fa[i][j] = fa[fa[i][j-1]][j-1];
}
if(dp[m] < k){
cout << -1 << endl;
exit(0);
}
st.clear();
st.insert({1, INF});
int cnt = 0;
int curans = dp[m];
// cout << fa[5][1] << endl;
// cout << get(3, 15) << endl;
for(int i = 0; i<n; i++){
if(cnt >= k) break;
auto it = st.lower_bound(arr[i]);
if(it == st.end() || (*it)[0] > arr[i][0]){
if(it == st.begin()) continue;
--it;
}
if((*it)[1] < arr[i][1]) continue;
int l1 = (*it)[0], l2 = arr[i][0], r2 = arr[i][1], r1 = (*it)[1];
int prvans = curans;
curans -= get(l1, r1);
curans += get(l1, l2); curans += get(r2, r1);
curans++;
if(curans >= k) cout << i+1 << endl, cnt++, st.erase(it), st.insert({l1, l2}), st.insert({r2, r1});
else curans = prvans;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |