| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 623242 | cheissmart | 사탕 분배 (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "candies.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 2e5 + 7;
const ll oo = 1e18;
int c[N], n, q;
V<pi> ev[N];
struct node {
ll mn, mx, lz;
node() {
mn = mx = lz = 0;
}
} t[N * 4];
void apply(int v, ll x) {
t[v].lz += x;
t[v].mn += x;
t[v].mx += x;
}
void push(int v) {
apply(v * 2, t[v].lz);
apply(v * 2 + 1, t[v].lz);
t[v].lz = 0;
}
void pull(int v) {
t[v].mn = min(t[v * 2].mn, t[v * 2 + 1].mn);
t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
}
void add(int l, int r, int x, int v = 1, int tl = 0, int tr = q + 1) {
if(l <= tl && tr <= r) {
apply(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
pull(v);
}
ll qmin(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
if(l <= tl && tr <= r)
return t[v].mn;
int tm = (tl + tr) / 2;
ll res = oo;
if(l < tm) res = min(res, qmin(l, r, v * 2, tl, tm));
if(r > tm) res = min(res, qmin(l, r, v * 2 + 1, tm, tr));
return res;
}
ll qmax(int l, int r, int v = 1, int tl = 0, int tr = q + 1){
if(l <= tl && tr <= r)
return t[v].mx;
int tm = (tl + tr) / 2;
ll res = -oo;
if(l < tm) res = max(res, qmax(l, r, v * 2, tl, tm));
if(r > tm) res = max(res, qmax(l, r, v * 2 + 1, tm, tr));
return res;
}
vi distribute_candies(vi _c, vi _l, vi _r, vi _v) {
n = SZ(_c), q = SZ(_l);
for(int i = 0; i < n; i++)
c[i] = _c[i];
vi ans(n);
for(int i = 1; i <= q; i++) {
int l = _l[i - 1], r = _r[i - 1], v = _v[i - 1];
ev[l].EB(i, v);
ev[r + 1].EB(i, -v);
}
for(int i = 0; i < n; i++) {
for(auto [pos, val]:ev[i])
add(pos, q + 1, val);
ll final = qmax(q, q + 1);
ll mx = qmax(0, q + 1);
ll mn = qmin(0, q + 1);
if(mx - mn <= c[i]) {
ans[i] = final - mn;
} else {
int lb = 0, rb = q;
while(lb <= rb) {
int mb = (lb + rb) / 2;
ll mx = qmax(mb, q + 1);
ll mn = qmin(mb, q + 1);
if(mx - mn <= c[i])
rb = mb - 1;
else
lb = mb + 1;
}
ll mx = qmax(rb, q + 1);
ll mn = qmin(rb, q + 1);
assert(mx - mn > c[i]);
ll val = qmax(rb, rb + 1);
if(val == mx) {
ans[i] = final - mn;
} else {
ans[i] = final - (mx - c[i]);
}
}
}
return ans;
}