| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 521344 | tkwiatkowski | Joker (BOI20_joker) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Zadanie: Wiring
Autor: Tomasz Kwiatkowski
*/
#include <bits/stdc++.h>
#include "wiring.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
const int BASE = 1<<17;
long long segTree[2*BASE + 7];
long long lazy[2*BASE + 7];
void Update(int v)
{
segTree[2*v] += lazy[v];
segTree[2*v + 1] += lazy[v];
lazy[2*v] += lazy[v];
lazy[2*v + 1] += lazy[v];
lazy[v] = 0;
}
void Add(int a, int b, long long val, int v = 1, int l = 0, int r = BASE - 1)
{
if (b < l || r < a)
return;
if (a <= l && r <= b) {
segTree[v] += val;
lazy[v] += val;
return;
}
Update(v);
int mid = (l + r) / 2;
Add(a, b, val, 2*v, l, mid);
Add(a, b, val, 2*v + 1, mid + 1, r);
segTree[v] = min(segTree[2*v], segTree[2*v + 1]);
}
void Clear(int a, int b, int v = 1, int l = 0, int r = BASE - 1)
{
segTree[v] = 1e18;
lazy[v] = 0;
if (l == r)
return;
int mid = (l + r) / 2;
if (l <= b)
Clear(a, b, 2*v, l, mid);
if (mid + 1 <= b)
Clear(a, b, 2*v + 1, mid + 1, r);
}
long long min_total_length(vector<int> r, vector<int> b)
{
for (int i = 0; i < 2*BASE; ++i)
segTree[i] = 1e18;
int n = r.size();
int m = b.size();
int i, j;
i = j = 0;
vector<int> x;
vector<bool> col;
while (i < n && j < m)
col.pb(r[i] < b[j]), x.pb((r[i] < b[j] ? r[i++] : b[j++]));
while (i < n)
col.pb(1), x.pb(r[i++]);
while (j < m)
col.pb(0), x.pb(b[j++]);
segTree[1] = 0;
long long ans = 0;
int prv_k = 0;
x.pb(x.back());
col.pb(!col.back());
for (int i = 0; i < n+m;) {
//printf("starting: i = %d\n", i);
int d = (i ? x[i] - x[i - 1] : 0);
int j = i;
int k = 0;
vector<long long> dp;
dp.pb(segTree[1]);
//printf("dp: %lld\n", dp.back());
long long sum = 0;
long long tmp = 0;
while (j < n+m && col[j] == col[i]) {
++k;
Add(k, BASE - 1, -d);
if (col[j + 1] == col[i]) {
sum += x[j + 1] - x[j];
//printf("sum = %lld\n", sum);
tmp += sum;
}
dp.pb(tmp + segTree[1]);
//printf("dp: %lld + %lld\n", tmp, segTree[1]);
++j;
}
Clear(0, prv_k + 1);
tmp = 0;
sum = 0;
ans = dp[dp.size()-1] + tmp + (ll)(dp.size()-1)*d;
for (size_t a = 0; a < dp.size(); ++a) {
Add(a, a, -(ll)1e18 + dp[dp.size()-1 - a] + tmp + (ll)a*(x[j] - x[j - 1]) + (ll)(dp.size()-1 - a)*d);
//printf("Add %lu: %lld + %lld + %lld + %lld\n", a, dp[dp.size()-1 - a], (ll)a*(x[j] - x[j - 1]), tmp, (ll)(dp.size()-1 - a)*d);
if (a > 0) {
sum += x[j - a] - x[j - a - 1];
tmp += sum;
}
}
prv_k = k;
i = j;
}
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(0), cin.tie(0);
// return 0;
// }