이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 1e5 + 5;
int n, k;
int l[N], r[N], ans[N], L[N][19], R[N][19];
int getl(int idx, int rpr) {
int ret = 0;
if (!idx) return ret;
for (int j = 17; j >= 0; --j) {
if (!L[idx][j]) continue;
if (rpr <= l[L[idx][j]]) {
ret += (1 << j);
idx = L[idx][j];
}
}
return ret;
}
int getr(int idx, int lnx) {
int ret = 0;
if (!idx) return ret;
for (int j = 17; j >= 0; --j) {
if (!R[idx][j]) continue;
if (r[R[idx][j]] <= lnx) {
ret += (1 << j);
idx = R[idx][j];
}
}
return ret;
}
vector < int > res;
set < pair < int , int > > stl, str;
set < pair < int , int > > :: iterator itl, itr;
bool check_add(int id) {
int rpr = 0, lnx = 1e9, idn = 0, idp = 0;
itl = stl.lower_bound({r[id], -1});
itr = str.lower_bound({l[id], -1});
if (itl != stl.end()) lnx = (*itl).f, idn = (*itl).s;
if (itr != str.begin()) --itr, rpr = (*itr).f, idp = (*itr).s;
itl = stl.lower_bound({l[id], -1});
itr = str.lower_bound({l[id] + 1, -1});
if (itl != stl.end() && l[(*itl).s] < r[id]) return false;
if (itr != str.end() && r[(*itr).s] <= r[id]) return false;
int res = getl(id, rpr) + 1 + getr(id, lnx);
int resA = getl(idp, 0) + (idp != 0);
int resB = getr(idn, 1e9) + (idn != 0);
if (resA + res + resB >= k) return true;
return false;
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> n >> k;
vector < pair < pair < int , int > , int > > s;
map < int , int > f;
vector < int > g;
for (int i = 1; i <= n; ++i) {
cin >> l[i] >> r[i];
g.pb(l[i]), g.pb(r[i]);
}
sort(g.begin(), g.end());
g.erase(unique(g.begin(), g.end()), g.end());
for (int i = 0; i < g.size(); ++i) {
f[g[i]] = i + 1;
}
int sz = g.size();
for (int i = 1; i <= n; ++i) {
l[i] = f[l[i]], r[i] = f[r[i]];
s.pb({{l[i], 1}, i});
s.pb({{r[i], 0}, i});
}
int rm = 1e9, idr = 0;
sort(s.begin(), s.end());
for (int i = s.size() - 1; i >= 0; --i) {
int id = s[i].s, tp = s[i].f.s;
if (tp && r[id] < rm) rm = r[id], idr = id;
if (!tp) R[id][0] = idr;
}
int lm = 0, idl = 0;
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); ++i) {
int id = s[i].s, tp = s[i].f.s;
if (!tp && lm < l[id]) lm = l[id], idl = id;
if (tp) L[id][0] = idl;
}
for (int j = 1; j <= 17; ++j)
for (int i = 1; i <= n; ++i) {
L[i][j] = L[L[i][j - 1]][j - 1];
R[i][j] = R[R[i][j - 1]][j - 1];
}
for (int i = 1; i <= n; ++i)
if (check_add(i)) {
stl.insert({l[i], i});
str.insert({r[i], i});
res.pb(i);
}
if (res.size() < k) cout << -1 << "\n";
else {
for (int i = 0; i < k; ++i)
cout << res[i] << "\n";
}
}
컴파일 시 표준 에러 (stderr) 메시지
event2.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
70 | main () {
| ^~~~
event2.cpp: In function 'int main()':
event2.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < g.size(); ++i) {
| ~~^~~~~~~~~~
event2.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < s.size(); ++i) {
| ~~^~~~~~~~~~
event2.cpp:124:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
124 | if (res.size() < k) cout << -1 << "\n";
| ~~~~~~~~~~~^~~
event2.cpp:88:6: warning: unused variable 'sz' [-Wunused-variable]
88 | int sz = g.size();
| ^~
# | 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... |