이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int MAXN = 4e5 + 5;
const ll INF = 1e15;
struct Node {
ll mini, maks, diff, lazy;
Node(ll mini, ll maks, ll diff, ll lazy) :
mini(mini), maks(maks), diff(diff), lazy(lazy) {}
Node() : mini(INF), maks(-INF), diff(-INF), lazy(0) {}
};
class Tournament {
int offset;
vector <Node> tour;
public:
Tournament(int n) {
for (offset = 1; offset < n; offset *= 2);
tour.resize(2 * offset);
}
Node merge(Node lhs, Node rhs) {
return Node(min(lhs.mini, rhs.mini), max(lhs.maks, rhs.maks), max(max(lhs.diff, rhs.diff), rhs.maks - lhs.mini), 0);
}
void prop(int x) {
tour[x].mini += tour[x].lazy;
tour[x].maks += tour[x].lazy;
if (x < offset) {
tour[2 * x].lazy += tour[x].lazy;
tour[2 * x + 1].lazy += tour[x].lazy;
}
tour[x].lazy = 0;
}
void refresh(int x) {
tour[x] = merge(tour[2 * x], tour[2 * x + 1]);
}
void update(int x, int lo, int hi, int from, int to, int val) {
prop(x);
if (lo >= to || hi <= from)
return;
if (lo >= from && hi <= to) {
tour[x].lazy += val;
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(2 * x, lo, mid, from, to, val);
update(2 * x + 1, mid, hi, from, to, val);
refresh(x);
}
void update(int x, int val) {
update(1, 0, offset, x, offset, val);
}
void modify(int x, int lo, int hi, int pos, int val) {
prop(x);
if (lo > pos || hi <= pos)
return;
if (hi - lo == 1) {
tour[x].mini += val - INF;
tour[x].maks += val + INF;
return;
}
int mid = (lo + hi) / 2;
modify(2 * x, lo, mid, pos, val);
modify(2 * x + 1, mid, hi, pos, val);
refresh(x);
}
void modify(int x, int val) {
modify(1, 0, offset, x, val);
}
ll get() {
prop(1);
return max(tour[1].diff, 0ll);
}
};
int N, M, D;
int pos[MAXN];
pii p[MAXN];
void load() {
scanf("%d%d%d", &N, &M, &D);
for (int i = 0; i < N + M; i++) {
scanf("%d", &p[i].first);
p[i].second = i;
}
}
void solve() {
sort(p, p + N + M);
for (int i = 0; i < N + M; i++)
pos[p[i].second] = i;
Tournament solver(N + M);
for (int i = 0; i < N + M; i++) {
solver.modify(pos[i], -p[pos[i]].first);
solver.update(pos[i], D);
ll ans = solver.get();
if (i >= N)
printf("%lld%s", ans / 2, ans % 2 ? ".5 " : " ");
}
puts("");
}
int main() {
load();
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void load()':
Main.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d%d%d", &N, &M, &D);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &p[i].first);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |