# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
171365 | alexandra_udristoiu | Wiring (IOI17_wiring) | C++14 | 48 ms | 9208 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include "wiring.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static long long d[DIM], sp[DIM];
pair<int, int> v[DIM];
pair<int, long long> dq[DIM];
long long min_total_length(vector<int> r, vector<int> b) {
int n, m, i, j, curr, prv, ind, p, u;
long long sum1, sum2, minim;
n = r.size();
m = b.size();
i = j = 0;
while(i < n && j < m){
if(r[i] < b[j]){
v[i + j + 1] = make_pair(r[i], 0);
i++;
}
else{
v[i + j + 1] = make_pair(b[j], 1);
j++;
}
}
for(; i < n; i++){
v[i + j + 1] = make_pair(r[i], 0);
}
for(; j < m; j++){
v[i + j + 1] = make_pair(b[j], 1);
}
n += m;
for(i = 1; i <= n; i++){
sp[i] = sp[i - 1] + v[i].f;
}
prv = 1;
sum1 = v[1].f;
sum2 = 0;
for(i = 2; i <= n; i++){
if(v[i].s != v[i - 1].s){
curr = i;
break;
}
else{
d[i] = 10000000000000LL;
sum1 += v[i].f;
}
}
for(; i <= n; i++){
sum2 += v[i].f;
d[i] = sum2 - sum1;
if(i - curr + 1 < curr - prv){
d[i] += ( (curr - prv) - (i - curr + 1) ) * 1LL * v[curr].f;
}
else{
d[i] -= ( (i - curr + 1) - (curr - prv) ) * 1LL * v[curr - 1].f;
}
if(v[i + 1].s != v[i].s){
break;
}
}
for(i = i + 1; i <= n; i++){
if(v[i - 1].s != v[i].s){
prv = curr;
curr = i;
p = 1;
u = 0;
for(j = i - 1; j >= prv; j--){
if(d[j - 1] == 0){
break;
}
sum1 = d[j - 1] - sp[i - 1] + sp[j - 1] + v[i].f * 1LL * (i - j);
while(p <= u && dq[u].s > sum1){
u--;
}
dq[++u] = make_pair(j, sum1);
}
minim = min(d[i - 1], d[i - 2]) + v[i].f - v[i - 1].f;
if(dq[p].f == i - 1){
p++;
}
if(p <= u){
d[i] = min(minim, dq[p].s);
}
else{
d[i] = minim;
}
ind = i - 1;
}
else{
minim += v[i].f - v[curr - 1].f;
if(i - curr + 1 <= curr - prv){
ind--;
minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]);
if(dq[p].f == ind){
p++;
}
}
if(p <= u){
d[i] = min(minim, dq[p].s + sp[i] - sp[curr] - v[curr].f * 1LL * (i - curr) );
}
else{
d[i] = minim;
}
}
}
return d[n];
}
Compilation message (stderr)
# | 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... |