이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 2e5 + 5;
const int inf = 1e9+7;
int n, h[N], a[N], b[N], q, l[N], r[N], ans[N];
vector<int> events[N + N];;
vector<ii> Q[N];
struct node {
int dp, h, x, lazy;
node(int dp = -inf, int h = -inf, int x = inf):
dp(dp), h(h), x(x), lazy(inf) {}
} t[N << 2];
void upd(int node, int x) {
t[node].x = min(t[node].x, x);
t[node].dp = max(t[node].dp, t[node].h - t[node].x);
}
void shift(int node) {
if(t[node].lazy == inf) return;
upd(node << 1, t[node].lazy);
upd(node << 1 | 1, t[node].lazy);
t[node].lazy = inf;
}
void seth(int node, int l, int r, int i, int H) {
if(l == r) {
t[node].h = H;
t[node].dp = H - t[node].x;
return;
}
int m = l + r >> 1;
if(i <= m) seth(node << 1, l, m, i, H);
else seth(node << 1 | 1, m + 1, r, i, H);
t[node].h = max(t[node << 1].h, t[node << 1 | 1].h);
}
void setx(int node, int l, int r, int i, int j, int x) {
if(r < i || l > j || x > t[node].x || t[node].h == -inf) return;
if(i <= l && r <= j) {
upd(node, x);
return;
}
shift(node);
int m = l + r >> 1;
setx(node << 1, l, m, i, j, x);
setx(node << 1 | 1, m + 1, r, i, j, x);
t[node].dp = max(t[node << 1].dp, t[node << 1 | 1].dp);
}
int get(int node, int l, int r, int i, int j) {
if(r < i || l > j) return -1;
if(i <= l && r <= j) return t[node].dp;
shift(node);
int m = l + r >> 1;
return max(get(node << 1, l, m, i, j),
get(node << 1 | 1, m + 1, r, i, j));
}
void run() {
for(int i = 1; i <= q; ++i)
Q[r[i]].emplace_back(l[i], i);
for(int i = 1; i <= n; ++i) {
events[i + a[i]].push_back(i);
events[i + b[i] + 1].push_back(-i);
for(int j : events[i]) {
if(j > 0) {
seth(1, 1, n, j, h[j]);
} else {
seth(1, 1, n, -j, -inf);
}
}
if(i > a[i])
setx(1, 1, n, max(1, i - b[i]), i - a[i], h[i]);
for(auto &it : Q[i]) {
ans[it.second] = max(ans[it.second], get(1, 1, n, it.first, i));
}
}
}
int main(int argc, char const *argv[]) {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d %d %d", &h[i], &a[i], &b[i]);
}
scanf("%d", &q);
for(int i = 1; i <= q; ++i) {
scanf("%d %d", &l[i], &r[i]);
ans[i] = -1;
}
run();
reverse(h + 1, h + n + 1);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
for(int i = 1; i <= q; ++i) {
l[i] = n + 1 - l[i];
r[i] = n + 1 - r[i];
swap(l[i], r[i]);
}
for(int i = 1; i <= 4 * n; ++i)
t[i] = node();
for(int i = 1; i <= n; ++i) {
Q[i].clear();
events[i].clear();
}
run();
for(int i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
}
}
컴파일 시 표준 에러 (stderr) 메시지
antennas.cpp: In function 'void seth(int, int, int, int, int)':
antennas.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
antennas.cpp: In function 'void setx(int, int, int, int, int, int)':
antennas.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
antennas.cpp: In function 'int get(int, int, int, int, int)':
antennas.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
antennas.cpp: In function 'int main(int, const char**)':
antennas.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &h[i], &a[i], &b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l[i], &r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |