이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+7;
int n, k;
vector<pair<int, int>> events;
vector<int> succ;
int dfs(int nd, int lim){
if(nd == -1) return 0;
if(events[nd].sc > lim) return 0;
return dfs(succ[nd], lim)+1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
events.resize(n);
succ.resize(n, -1);
for(auto &p: events) cin >> p.f >> p.sc;
vector<pair<int, int>> sth;
for(int i = 0; i < n; i++){
sth.pb({events[i].f, i+1});
sth.pb({events[i].sc, -i-1});
}
sort(sth.begin(), sth.end());
int mn = inf, cur = -1, start = -1, start_end = inf;
for(int i = (int)sth.size()-1; i >= 0; i--){
int in = sth[i].sc;
if(in < 0){
in*=-1;
in--;
if(events[in].sc == start_end) start = min(start, in);
else if(events[in].sc < start_end) start_end = events[in].sc, start = in;
succ[in] = cur;
}
else{
in--;
if(events[in].sc == mn) cur = min(cur, in);
else if(events[in].sc < mn) mn = events[in].sc, cur = in;
}
}
int sum = dfs(start, inf);
set<array<int, 4>> ss;
ss.insert({inf, 0, start, sum});
vector<int> ans;
int kk = k;
for(int i = 0; i < n; i++){
if(kk == 0) break;
auto it = ss.lower_bound({events[i].sc, 0, 0, 0});
if(it == ss.end() || (*it)[1] > events[i].f) continue;
auto [r, l, st, cnt] = *it;
int a = dfs(st, events[i].f);
int b = dfs(succ[i], r);
if(a+b+sum-cnt+1 < kk) continue;
ans.pb(i);
sum-=cnt;
sum+=a+b;
ss.erase(it);
ss.insert({events[i].f, l, st, a});
ss.insert({r, events[i].sc, succ[i], b});
kk--;
}
if(ans.size() != k) cout << "-1\n", exit(0);
for(int x: ans) cout << x+1 << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
event2.cpp: In function 'int main()':
event2.cpp:76:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
76 | if(ans.size() != k) cout << "-1\n", exit(0);
| ~~~~~~~~~~~^~~~
# | 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... |