Submission #406890

#	Time	Username	Problem	Language	Result	Execution time	Memory
406890		pliam	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	2060 ms	353288 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000005
typedef long long ll;

ll pos[2*MAXN];
ll st[8*MAXN],lazy[8*MAXN];
int n,k;
ll l;
ll ans;

void update(int from,int to,ll val,int v=1,int start=0,int end=2*n){
    if(start==from&&end==to){
        lazy[v]+=val;
        st[v]+=val;
        return;
    }
    int mid=(start+end)/2;
    if(lazy[v]){
        //propagate
        update(start,mid,lazy[v],2*v,start,mid);
        update(mid+1,end,lazy[v],2*v+1,mid+1,end);
        lazy[v]=0;
    }
    if(to<=mid){
        update(from,to,val,2*v,start,mid);
    }else if(from>mid){
        update(from,to,val,2*v+1,mid+1,end);
    }else{
        update(from,mid,val,2*v,start,mid);
        update(mid+1,to,val,2*v+1,mid+1,end);
    }
    st[v]=min(st[2*v],st[2*v+1]);
}

ll query(int from,int to,int v=1,int start=0,int end=2*n){
    if(start==from&&end==to){
        return st[v];
    }
    int mid=(start+end)/2;
    if(lazy[v]){
        //propagate
        update(start,mid,lazy[v],2*v,start,mid);
        update(mid+1,end,lazy[v],2*v+1,mid+1,end);
        lazy[v]=0;
    }
    if(to<=mid){
        return query(from,to,2*v,start,mid);
    }else if(from>mid){
        return query(from,to,2*v+1,mid+1,end);
    }else{
        return min(query(from,mid,2*v,start,mid),query(mid+1,to,2*v+1,mid+1,end));
    }
}

ll dist(ll x){
    return min(x,l-x);
}

int modn(int i){
    return (i<=n)?i:(i-n);
}

ll c(int i){
    return dist(pos[modn(i)])+pos[i];
}

ll d(int i){
    return dist(pos[modn(i+1)])-pos[i+1];
}

ll q(int s,int i){//dp[i] with start s
    return c(i)+query(max(s-1,i-k),i-1);
}

ll dp(int i){
    return query(i,i)-d(i);
}

long long delivery(int N, int K, int L, int positions[]) {
    n=N;
    k=K;
    l=L;
    if(N==1){
        return 2*dist(positions[0]);
    }
    for(int i=1;i<=n;i++){
        pos[i]=positions[i-1];
    }
    for(int i=n+1;i<=2*n;i++){
        pos[i]=pos[i-n]+l;
    }
    update(0,0,d(0));//base case->dp[s-1]=dp[0]=0
    for(int i=1;i<=n;i++){
        update(i,i,q(1,i)+d(i));
    }
    ans=dp(n);
    for(int s=2;s<=n;s++){
        update(s-1,s+n-2,-dp(s-1));//0-dp[s-1]
        update(s+n-1,s+n-1,q(s,s+n-1)+d(s+n-1));//make dp[s+n-1]
        ans=min(ans,dp(s+n-1));
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30