제출 #1227404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227404		PVM_pvm	나일강 (IOI24_nile)	C++20	67 / 100	2092 ms	10568 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100'007
int n;
struct art
{
    long long w,a,b;
} ar[MAXN];
bool cmp(art &a, art &b)
{
    return a.w<b.w;
}
int lr[MAXN];
long long sufs[MAXN];
long long dp[MAXN];
long long mnn,seg[4*MAXN];
void Initialise(int ind, int l, int r)
{
    seg[ind]=LONG_LONG_MAX;
    if (l==r)
    {
        return;
    }
    int mid=(l+r)/2;
    Initialise(ind*2,l,mid);
    Initialise(ind*2+1,mid+1,r);
}
void Update(int ind, int l, int r, int pos, long long st)
{
    if (l==r)
    {
        seg[ind]=st;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid) Update(ind*2,l,mid,pos,st);
    else Update(ind*2+1,mid+1,r,pos,st);
    seg[ind]=min(seg[ind*2],seg[ind*2+1]);
}
void Query(int ind, int l, int r, int ql, int qr)
{
    if (ql<=l && qr>=r)
    {
        mnn=min(mnn,seg[ind]);
        return;
    }
    int mid=(l+r)/2;
    if (ql<=mid) Query(ind*2,l,mid,ql,qr);
    if (qr>=mid+1) Query(ind*2+1,mid+1,r,ql,qr);
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E)
{

    int Q = (int)E.size();
    n=A.size();
    for (int q=0;q<n;q++) ar[q]={W[q],A[q],B[q]};
    sort(ar,ar+n,cmp);
    vector<long long> R(Q);
    for (int curq=0;curq<Q;curq++)
    {
        int d=E[curq];
        lr[0]=0;
        for (int q=1;q<n;q++)
        {
            lr[q]=lr[q-1];
            while ((ar[q].w-ar[lr[q]].w)>d) lr[q]++;
        }
        sufs[n]=0;
        sufs[n-1]=ar[n-1].a;
        for (int q=n-2;q>=0;q--) sufs[q]=sufs[q+1]+ar[q].a;
        Initialise(1,0,n);
        dp[0]=0;
        Update(1,0,n,0,dp[0]+ar[0].b+sufs[1]);
        dp[1]=ar[0].a;
        Update(1,0,n,1,dp[1]+ar[1].b+sufs[2]);
        for (int q=2;q<=n;q++) ///
        {
            dp[q]=dp[q-1]+ar[q-1].a;
            if (lr[q-1]!=q-1)
            {
                mnn=LONG_LONG_MAX;
                Query(1,0,n,lr[q-1],q-2);
                mnn-=sufs[q-1];
                mnn+=ar[q-1].b;
                //cout<<q<<" "<<mnn<<" xx\n";
                if (mnn<dp[q]) dp[q]=mnn;
            }
            Update(1,0,n,q,dp[q]+ar[q].b+sufs[q+1]);
            /*long long buf=0;
            for (int w=q-2;w>=0;w--)
            {
                if ((ar[q-1].w-ar[w].w)>d) break;
                long long cur=dp[w]+(ar[q-1].b)+ar[w].b+buf;
                if (cur<dp[q]) dp[q]=cur;
                buf+=ar[w].a;
            }*/
            //cout<<dp[q]<<" t ";
        }
        //cout<<"\n";
        R[curq]=dp[n];
    }
    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18