Submission #757047

#	Time	Username	Problem	Language	Result	Execution time	Memory
757047		Rafi22	Wiring (IOI17_wiring)	C++14	0 / 100	5 ms	8532 KiB

wiring

#include <bits/stdc++.h>


using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=100000000000000007;

const int N=200007,pot=1<<18;

ll seg[2*pot+7][2];
ll DP[N];
ll P[N],P1[N];
ll S[N],S1[N];

ll que(int v,int a,int b,int l,int r,int i)
{
    if(a<=l&&b>=r) return seg[v][i];
    if(r<a||l>b) return infl;
    return min(que(2*v,a,b,l,(l+r)/2,i),que(2*v+1,a,b,(l+r)/2+1,r,i));
}
void ins(int v,ll x,int i)
{
    v+=pot-1;
    seg[v][i]=x;
    while(v>1)
    {
        v/=2;
        seg[v][i]=min(seg[2*v][i],seg[2*v+1][i]);
    }
}

ll min_total_length(vector<int>r,vector<int>b)
{
    vector<pair<ll,int>>V;
    int n=sz(r),m=sz(b);
    for(int i=0;i<n;i++) V.pb({r[i],0});
    for(int i=0;i<m;i++) V.pb({b[i],1});
    sort(all(V));
    for(ll i=1;i<n+m;i++)
    {
        P[i]=P[i-1]+V[i].st-V[i-1].st;
        P1[i]=P1[i-1]+(V[i].st-V[i-1].st)*i;
    }
    for(int i=n+m-1;i>0;i--)
    {
        S[i]=S[i+1]+V[i].st-V[i-1].st;
        S1[i]=S1[i+1]+(V[i].st-V[i-1].st)*(n+m-i);
    }
    for(int i=1;i<2*pot;i++) seg[i][0]=infl,seg[i][1]=infl;
    int L=1,R=0;
    for(int i=0;i<n+m;i++)
    {
        if(i>0&&V[i].nd!=V[i-1].nd)
        {
            L=R+1;
            R=i;
            for(int j=L;j<=R;j++)
            {
                ll X=P1[R-1]-P1[j-1]-(P[R-1]-P[j-1])*(j-1);
                ins(j,DP[j-1]+X,0);
                ins(j,DP[j-1]+X+(V[R].st-V[R-1].st)*(R-j+1),1);
            }
        }
        DP[i+1]=infl;
        if(R>0)
        {
            ll k=i+1-R;
            ll X=S1[R+1]-S1[i+1]-(S[R+1]-S[i+1])*(n+m-i-1);
            DP[i+1]=min(DP[i+1],que(1,L,R-k+2,1,pot,0)+X+k*(V[R].st-V[R-1].st));
            DP[i+1]=min(DP[i+1],que(1,R-k+3,R,1,pot,1)+X);
        }
    }
    return DP[n+m];
}
/*

int main()
{
    cout<<min_total_length({1, 2, 3, 7},{0, 4, 5, 9, 10});
    return 0;
}
*/

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