| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1321084 | kasamchi | 전선 연결 (IOI17_wiring) | C++20 | 0 ms | 0 KiB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val, tag;
};
vector<Node> SEG;
#define L(x) ((x) + (x))
#define R(x) (L(x) + 1)
void push(int id) {
SEG[L(id)].val += SEG[id].tag;
SEG[R(id)].val += SEG[id].tag;
SEG[L(id)].tag += SEG[id].tag;
SEG[R(id)].tag += SEG[id].tag;
SEG[id].tag = 0;
}
void mod(int ml, int mr, int l, int r, long long x, int id) {
if (ml <= l && r <= mr) {
SEG[id].val += x;
SEG[id].tag += x;
} else {
push(id);
int m = l + (r - l) / 2;
if (ml <= m) {
mod(ml, mr, l, m, x, L(id));
} else {
mod(ml, mr, m + 1, r, x, R(id));
}
SEG[id].val = min(SEG[L(id)].val, SEG[R(id)].val);
}
}
long long qry(int ql, int qr, int l, int r, int id) {
if (ql <= l && r <= qr) {
return SEG[id].val;
} else {
push(id);
int m = l + (r - l) / 2;
long long ret = 1e18;
if (ql <= m) {
ret = min(ret, qry(ql, qr, l, m, L(id)));
}
if (qr > m) {
ret = min(ret, qry(ql, qr, m + 1, r, R(id)));
}
}
}
long long min_total_length(vector<int> r, vector<int> b) {
int N = r.size() + b.size();
int ridx = 0, bidx = 0;
vector<int> pos = {0}, col = {0};
while (ridx < r.size() || bidx < b.size()) {
if (bidx == b.size()) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else if (ridx == r.size()) {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
} else if (r[ridx] < b[bidx]) {
pos.push_back(r[ridx]);
col.push_back(0);
ridx++;
} else {
pos.push_back(b[bidx]);
col.push_back(1);
bidx++;
}
}
vector<pair<int, int>> seg;
for (int i = 1; i <= N; ) {
int j = i;
while (j <= N && col[i] == col[j]) {
j++;
}
seg.push_back(make_pair(i, j - 1));
i = j;
}
vector<long long> pre(N + 1);
for (int i = 1; i <= N; i++) {
pre[i] = pre[i - 1] + pos[i];
}
vector<long long> dp(N + 1, (long long)1e18);
SEG.resize(N * 4);
for (int sid = 1; sid < seg.size(); sid++) {
int clb = seg[sid].first, crb = seg[sid].second;
int plb = seg[sid - 1].first, prb = seg[sid - 1].second;
int psz = prb - plb + 1;
vector<long long> dqb(psz);
for (int i = 0, p = plb; i < psz; i++, p++) {
dqb[i] += min(dp[p - 1], dp[p]);
dqb[i] += pre[p - 1] - pre[plb - 1];
}
vector<long long> dqd(psz);
dqd[0] = dqb[0];
for (int i = 1; i < psz; i++) {
dqd[i] = -dqb[i - 1] + dqb[i];
}
for (int c = clb; c <= crb; c++) {
int csz = c - clb + 1;
long long sum = 0;
sum += pre[c] - pre[clb - 1];
sum -= pre[prb] - pre[plb - 1];
if (psz <= csz) {
sum -= (long long)pos[prb] * (csz - psz);
} else {
sum += (long long)pos[clb] * (psz - csz);
}
if (sid == 1) {
dp[c] = sum;
} else {
vector<pair<pair<int, int>, long long>> ops;
mod(plb, plb, 1, N, sum, 1);
ops.push_back(make_pair(make_pair(plb, plb), sum));
if (1 <= psz - csz) {
mod(plb + 1, plb + (psz - csz), 1, N, -pos[clb], 1);
ops.push_back(make_pair(make_pair(plb + 1, plb + (psz - csz)), -pos[clb]));
}
if (max(0, psz - csz) + 1 < psz) {
mod(plb + max(0, psz - csz) + 1, plb + psz - 1, 1, N, -pos[prb], 1);
ops.push_back(make_pair(make_pair(plb + max(0, psz - csz) + 1, plb + psz - 1), -pos[prb]));
}
long long cur = 0;
for (int i = 0, p = plb; i < psz; i++, p++) {
cur += qry(p, p, 1, N, 1);
dp[c] = min(dp[c], cur);
}
for (auto &[pos, val] : ops) {
dqd[pos] -= val;
}
}
}
}
return dp[N];
}