Submission #889957

#	Time	Username	Problem	Language	Result	Execution time	Memory
889957		winter0101	Wiring (IOI17_wiring)	C++14	100 / 100	116 ms	58808 KiB

wiring

#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
long long f[maxn];
const long long inf=1e18;
/*
2 type of update
rrrrbrrrr (just 1 blue)
rrrrbbbb (red>=blue or blue>=red)
*/
long long l[maxn],r[maxn];
vector<long long>del1[maxn],del2[maxn],del3[maxn],add1[maxn],add2[maxn],add3[maxn];//
long long pf[maxn];
long long min_total_length(vector<int> red, vector<int> blue) {
    int n=sz(red),m=sz(blue);
    vector<pli>a;
    a.pb({0,0});
    for1(i,0,n-1)a.pb({red[i]+1,1});
    for1(i,0,m-1)a.pb({blue[i]+1,0});
    sort(all(a));
    f[0]=0;
    n=n+m;
    for1(i,1,n)pf[i]=pf[i-1]+a[i].fi;
    for1(i,1,n)f[i]=inf;
    for2(i,n,1){
    r[i]=i;
    if (i<n&&a[i].se==a[i+1].se)r[i]=r[i+1];
    }
    for1(i,1,n){
    l[i]=i;
    if (i>1&&a[i].se==a[i-1].se)l[i]=l[i-1];
    }
    multiset<long long>f1,f2,f3;//f1 mean opposite larger, f2 opposite smaller and f3 just 1 opposite
    for1(i,0,n){
    for (auto v:add1[i]){
    f1.insert(v);
    //if (i==n)cerr<<v<<'\n';
    }
    for (auto v:add2[i])f2.insert(v);
    for (auto v:add3[i])f3.insert(v);
    if (i>0){
    if (!f1.empty()){
    auto it=f1.begin();
    long long cost=-a[l[i]].fi*(i-l[i]+1)+pf[i]-pf[l[i]-1];
    f[i]=min(f[i],(*it)+cost);
    }
    if (!f2.empty()){
    auto it=f2.begin();
    f[i]=min(f[i],(*it)+pf[i]-pf[l[i]-1]-a[l[i]-1].fi*(i-l[i]+1));
    }
    if (!f3.empty()){
    auto it=f3.begin();
    long long cost=1ll*pf[i]-pf[l[i]-1]-a[l[i]-1].fi*(i-l[i]+1);
    f[i]=min(f[i],(*it)+cost);
    }
    }
    for (auto v:del1[i])f1.erase(f1.find(v));
    for (auto v:del2[i])f2.erase(f2.find(v));
    for (auto v:del3[i])f3.erase(f3.find(v));
    if (i==n)break;
    //update for type 1
    if (r[i+1]+1<=n){
    long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[r[i+1]+1];
    add1[l2].pb(f[i]-(pf[r1]-pf[l1-1])+a[l2].fi*(r1-l1+1));
    //for (auto v:add1[n])cerr<<v<<'\n';
    del1[min(l2+(r1-l1+1)-1,r2)].pb(f[i]-(pf[r1]-pf[l1-1])+a[l2].fi*(r1-l1+1));
    }
    //update for type 2
    if (r[i+1]+1<=n){
    long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[r[i+1]+1];
    if (r2-l2+1>r1-l1+1){
    l2+=(r1-l1+1);
    add2[l2].pb(f[i]-(pf[r1]-pf[l1-1])+a[r1].fi*(r1-l1+1));
    del2[r2].pb(f[i]-(pf[r1]-pf[l1-1])+a[r1].fi*(r1-l1+1));
    }
    }
    //update for type 3
    if (r[i+1]+2<=n&&a[r[i+1]+2].se==a[i+1].se){
    long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[i+1]+1,l3=r[i+1]+2,r3=r[r[i+1]+2];
    long long cost=a[l2].fi*(r1-l1+1)-pf[r1]+pf[l1-1]+f[i];
    //cerr<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" "<<l3<<" "<<r3<<'\n';
    add3[l3].pb(cost);
    del3[r3].pb(cost);
    }
    }
    return f[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:95:44: warning: unused variable 'r2' [-Wunused-variable]
   95 |     long long l1=i+1,r1=r[i+1],l2=r[i+1]+1,r2=r[i+1]+1,l3=r[i+1]+2,r3=r[r[i+1]+2];
      |                                            ^~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45