Submission #1068688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068688		TlenekWodoru	Truck Driver (IOI23_deliveries)	C++17	0 / 100	63 ms	15952 KiB

deliveries

#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
    int b,c;
};
long long O[100009];
long long O1[100009],O2[100009];
long long Opref[100009],Osuff[100009];
int base;
long long Tre[1000000];
long long TrePref[1000000];
long long TreSuff[1000000];
long long Deliv[100009];
long long suma=0;
int n;
int TworzenieDrzewa(int x)
{
    x--;
    int u=1;
    while(x>0)
    {
        x>>=1;
        u<<=1;
    }
    return u;
}
void Punkt(int v, int dod, long long *TRE)
{
    v+=base;
    while(v>0)
    {
        TRE[v]+=dod;
        v>>=1;
    }
}
int PierwszyWiekszy(long long x)
{
    int v=1;
    while(v<base)
    {
        if(x-Tre[v*2]<0)
        {
            v=v*2;
        }
        else
        {
            x-=Tre[v*2];
            v=v*2+1;
        }
    }
    return v-base;
}
int PierwszyWiekszy2(long long x)
{
    int v=1;
    while(v<base)
    {
        if(x-Tre[v*2+1]<0)
        {
            v=v*2+1;
        }
        else
        {
            x-=Tre[v*2+1];
            v=v*2;
        }
    }
    return v-base;
}
long long Przedzial(int l, int p, long long *TRE)
{
    l+=base;
    p+=base;
    long long wyn=0;
    while(l<=p)
    {
        if(l%2==1)
        {
            wyn+=TRE[l];
            l++;
        }
        if(p%2==0)
        {
            wyn+=TRE[p];
            p--;
        }
        l>>=1;
        p>>=1;
    }
    return wyn;
}
void init(int N, vector<int> AA, vector<int> BB, vector<int> CC, vector<int> W)
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        //int a=AA[i];
        //int b=BB[i];
        int c=CC[i];
        O[i]=c;
    }
    for(int i=0;i<=n-2;i++)
    {
        O1[i+1]=O[i]+O1[i];
    }
    for(int i=n-1;i>=1;i--)
    {
        O2[i-1]=O[i-1]+O2[i];
    }
    base=TworzenieDrzewa(n);
    for(int i=0;i<n;i++)
    {
        Deliv[i]=W[i];
        suma+=Deliv[i];
        if(i==0){Deliv[i]++;}
        Punkt(i,O1[i]*Deliv[i],TrePref);
        Punkt(i,O2[i]*Deliv[i],TreSuff);
        if(i==0){Deliv[i]--;}
        Punkt(i,Deliv[i],Tre);
    }
}
long long max_time(int v, int x)
{
    int dod=x-Deliv[v];
    suma+=dod;
    Deliv[v]=x;
    if(v==0){Deliv[v]++;}
    Punkt(v,O1[v]*dod,TrePref);
    Punkt(v,O2[v]*dod,TreSuff);
    if(v==0){Deliv[v]--;}
    Punkt(v,dod,Tre);
    long long kand1,kand2,Ile1,Ile2;
    v=PierwszyWiekszy((suma>>1)-1);
    Ile1=Przedzial(0,v,Tre)+1;
    Ile2=suma-Ile1;
    kand1=Przedzial(0,v,TreSuff)-O2[v]*Ile1+Przedzial(v+1,base-1,TrePref)-O1[v]*Ile2;

    v=PierwszyWiekszy2((suma)>>1);
    Ile1=Przedzial(0,v,Tre)+1;
    Ile2=suma-Ile1;
    kand2=Przedzial(0,v,TreSuff)-O2[v]*Ile1+Przedzial(v+1,base-1,TrePref)-O1[v]*Ile2;
    return max(kand1,kand2)*2;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 21
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36