이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "wiring.h"
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
ll eval(ll a, ll b, int x) {
return a * x + b;
}
class segtree {
int n;
// ax + b
vl a, b;
vi ls, rs;
void _update(int k, ll na, ll nb) {
int l = ls[k], r = rs[k], m = (l + r) / 2;
if (l + 1 == r) {
if (eval(a[k], b[k], l) > eval(na, nb, l)) {
a[k] = na;
b[k] = nb;
}
return;
}
if (eval(a[k], b[k], l) <= eval(na, nb, l) and eval(a[k], b[k], r) <= eval(na, nb, r)) return;
if (eval(a[k], b[k], l) >= eval(na, nb, l) and eval(a[k], b[k], r) >= eval(na, nb, r)) {
a[k] = na;
b[k] = nb;
return;
}
if (eval(a[k], b[k], m) > eval(na, nb, m)) {
swap(a[k], na);
swap(b[k], nb);
}
if (eval(a[k], b[k], l) > eval(na, nb, l)) {
_update(2 * k, na, nb);
return;
}
if (eval(a[k], b[k], r) > eval(na, nb, r)) {
_update(2 * k + 1, na, nb);
return;
}
assert(false);
}
public:
segtree(int _n) {
n = 1;
while (n < _n) n *= 2;
a.assign(2 * n, 0);
b.assign(2 * n, linf);
ls.resize(2 * n);
rs.resize(2 * n);
rep(i, n) {
ls[n + i] = i;
rs[n + i] = i + 1;
}
rrep(i, n) {
ls[i] = ls[2 * i];
rs[i] = rs[2 * i + 1];
}
}
ll get(int i) {
assert(0 <= i and i < n);
int x = i;
i += n;
ll res = linf;
while (i >= 1) {
chmin(res, eval(a[i], b[i], x));
i >>= 1;
}
return res;
}
void update(int l, int r, ll na, ll nb) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
while (l < r) {
if (l & 1) _update(l++, na, nb);
if (r & 1) _update(--r, na, nb);
l >>= 1, r >>= 1;
}
}
};
ll min_total_length(vi r, vi b) {
int n = r.size();
int m = b.size();
ll ans = 0;
if (n >= m) {
rep(i, n - (m - 1)) ans += b[0] - r[i];
rep(i, m - 1) ans += b[i + 1] - r[n - (m - 1) + i];
} else {
rep(i, n - 1) ans += b[i] - r[i];
rep2(i, n - 1, m) ans += b[i] - r.back();
}
vector<pair<ll, int>> v;
rep(i, n) v.eb(r[i], 0);
rep(i, m) v.eb(b[i], 1);
sort(all(v));
vi ps;
rep(i, n + m - 1) if (v[i].second != v[i + 1].second) ps.pb(i + 1);
ps.pb(n + m);
vl sum_r(n + m + 1);
rep(i, n + m) {
sum_r[i + 1] = sum_r[i] + (v[i].second == 0 ? v[i].first : -v[i].first);
}
vl sum_b(n + m + 1);
rep(i, n + m) {
sum_b[i + 1] = sum_b[i] + (v[i].second == 1 ? v[i].first : -v[i].first);
}
// segtree st(n + m + 10);
// st.update(0, 1, 0, 0);
vl dp(n + m + 10, linf);
dp[0] = 0;
rep(i, n + m) {
// ll now = st.get(i);
ll now = dp[i];
if (i > 0) {
if (v[i - 1].second == 0) now += sum_r[i];
else now += sum_b[i];
}
auto it = upper_bound(all(ps), i);
int x = *it;
it++;
if (it == ps.end()) continue;
int y = *it;
ll sub;
if (v[i].second == 0) sub = sum_b[i];
else sub = sum_r[i];
int p = 2 * x - i;
if (y <= p) {
// st.update(x + 1, y + 1, -v[x].first, now + v[x].first * p - sub);
rep2(j, x + 1, y + 1) {
chmin(dp[j], -v[x].first * j + now + v[x].first * p - sub);
}
} else {
// st.update(x + 1, p + 1, -v[x].first, now + v[x].first * p - sub);
rep2(j, x + 1, p + 1) {
chmin(dp[j], -v[x].first * j + now + v[x].first * p - sub);
}
// st.update(p + 1, y + 1, -v[x - 1].first, now + v[x - 1].first * p - sub);
rep2(j, p + 1, y + 1) {
chmin(dp[j], -v[x - 1].first * j + now + v[x - 1].first * p - sub);
}
}
}
// ll res = st.get(n + m);
ll res = dp[n + m];
if (v.back().second == 0) res += sum_r[n + m];
else res += sum_b[n + m];
return res;
}
# | 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... |