이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int N = 1e5 + 5, M = 2e5 + 5, K = 20;
int n, m, k, q, x, y, mn[K][M], mx[K][M];
vector<pii> v;
vector<int> add[N], del[N];
multiset<int> msa;
multiset<int, greater<int>> msb;
struct segment {
struct node {
int mns, mxs;
node() : mns(INT_MAX), mxs(INT_MIN) {}
node(int mnval, int mxval) : mns(mnval), mxs(mxval) {}
friend node operator + (node a, node b) {
node res = node();
res.mns = min(a.mns, b.mns);
res.mxs = max(a.mxs, b.mxs);
return res;
}
} t[N * 4];
void build (int l, int r, int idx, int lf) {
if (l == r) return void(t[idx] = node(mn[lf][l], mx[lf][l]));
int mid = (l + r) >> 1;
build(l, mid, idx * 2 + 1, lf);
build(mid + 1, r, idx * 2 + 2, lf);
t[idx] = t[idx * 2 + 1] + t[idx * 2 + 2];
}
node qr (int l, int r, int idx, int tl, int tr) {
if (l > tr || r < tl) return node();
if (l >= tl && r <= tr) return t[idx];
int mid = (l + r) >> 1;
return qr(l, mid, idx * 2 + 1, tl, tr) + qr(mid + 1, r, idx * 2 + 2, tl, tr);
}
} segm[K];
void solve() {
scanf("%d %d", &x, &y);
if (mn[K - 1][x] > y || mx[K - 1][x] < y) return void(printf("-1\n"));
int l = x, r = x, ans = 0;
for (int i = K - 1; i >= 0; i--) {
int mni = segm[i].qr(1, n, 0, l, r).mns;
int mxi = segm[i].qr(1, n, 0, l, r).mxs;
if (mni <= y && mxi >= y) continue;
ans += (1 << i); l = mni; r = mxi;
}
printf("%d\n", ++ans);
}
int main() {
scanf("%d %d %d", &n, &k, &m); v.resize(m);
for (auto &[a, b]: v) scanf("%d %d", &a, &b);
for (int i = 0; i < m; i++) {
auto [a, b] = v[i];
if (a < b) continue;
add[max(a - k + 1, b)].emplace_back(i);
del[a].emplace_back(i);
}
for (int i = 1; i <= n; i++) {
for (auto &e: add[i]) msa.emplace(v[e].second);
mn[0][i] = (msa.empty() ? i : *msa.begin());
for (auto &e: del[i]) msa.erase(msa.find(v[e].second));
}
for (int i = 1; i <= n; i++) add[i].clear(), del[i].clear();
for (int i = 0; i < m; i++) {
auto [a, b] = v[i];
if (a > b) continue;
add[a].emplace_back(i);
del[min(a + k - 1, b)].emplace_back(i);
}
for (int i = 1; i <= n; i++) {
for (auto &e: add[i]) msb.emplace(v[e].second);
mx[0][i] = (msb.empty() ? i : *msb.begin());
for (auto &e: del[i]) msb.erase(msb.find(v[e].second));
}
segm[0].build(1, n, 0, 0);
for (int i = 1; i < K; i++) {
for (int j = 1; j <= n; j++) {
mn[i][j] = segm[i - 1].qr(1, n, 0, mn[i - 1][j], mx[i - 1][j]).mns;
mx[i][j] = segm[i - 1].qr(1, n, 0, mn[i - 1][j], mx[i - 1][j]).mxs;
}
segm[i].build(1, n, 0, i);
}
scanf("%d", &q);
while (q--) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void solve()':
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d %d", &n, &k, &m); v.resize(m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | for (auto &[a, b]: v) scanf("%d %d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |