Submission #839569

#	Time	Username	Problem	Language	Result	Execution time	Memory
839569		model_code	Truck Driver (IOI23_deliveries)	C++17	29 / 100	279 ms	27852 KiB

deliveries

// correct/solution-subtask4.cpp

#include "deliveries.h"

#include <iostream>
#include <vector>

#define MAXN 101000

using namespace std;

long long N, centroid, allSumW, ans, uValue, uFrom, flippedWT, allSumTxW;
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];
long long sumT[MAXN];

struct node{
    int a, b;
    long long w, sumWT, sumL, sumT;
    node* leftC;
    node* rightC;
};
node* tree;

node* build(int x, int y){
    node* p = new node;
    node* lc = nullptr;
    node* rc = nullptr;

    p->a = x; p->b = y; p->w = 0;
    p->sumWT = 0; p->sumL = 0; p->sumT = 0;
    if(x==y){
        p->w = W[x-1];
        p->sumWT = T[x-1] * sumW[x-1];
        p->sumT = T[x-1];
    } else {
        lc = build(x,(x+y)/2);
        rc = build((x+y)/2+1,y);
        p->w = lc->w + rc->w;
        p->sumWT = lc->sumWT + rc->sumWT;
        p->sumT = lc->sumT + rc->sumT;
    }
    p->leftC = lc; p->rightC = rc;

    return p;
}

long long sumValue(node* p){
	return p->sumWT + p->sumL * p->sumT;
}
void push_down(node* p){
	(p->leftC)->sumL += p->sumL;
	(p->rightC)->sumL += p->sumL;
	p->sumL = 0;
}
void update_node(node* p){
	p->sumWT = sumValue(p->leftC) + sumValue(p->rightC);
}

void update(node* p){
    p->w += uValue;
    if(p->a==p->b){
        p->sumL += uValue;
        return;
    }

    push_down(p);

    if(uFrom<=(p->a+p->b)/2){
        update(p->leftC);
    } else {
        (p->leftC)->sumL += uValue;
        update(p->rightC);
    }
    update_node(p);
}

int findCentroid(node* p){
    if(p->a==p->b){
        flippedWT += sumValue(p);
        return p->a-1;
    }

    push_down(p);
    update_node(p);

    if((p->rightC)->w >= uValue){
        flippedWT += sumValue(p->leftC);
        return findCentroid(p->rightC);
    }

    uValue -= (p->rightC)->w;
    return findCentroid(p->leftC);
}

void init(int NN, std::vector<int> /*UU*/, std::vector<int> /*VV*/, std::vector<int> TT, std::vector<int> WW){
	N = NN;
    for(int i=0; i<N-1; i++){
        T[i+1] = TT[i];
        sumT[i+1] = sumT[i] + T[i+1];
	}
	for(int i=0; i<N; i++){
		W[i] = WW[i];
	}
	W[0]++;

    for(int i=0; i<N; i++){
        allSumTxW += W[i] * sumT[i];
    }

    for(int i=N-1; i>=0; i--)
        sumW[i] = sumW[i+1] + W[i];
    allSumW = sumW[0];

    tree = build(1,N);
}

long long max_time(int S, int X){
	if(S==0) X++;

    long long diff = X - W[S];
    allSumTxW += diff * sumT[S];

    allSumW -= W[S];

	W[S] = X;
    allSumW += W[S];

    uFrom = S+1; uValue = diff; update(tree);

    uValue = (allSumW + 1)/2; flippedWT = 0;
    int cent = findCentroid(tree);

    return 2 * (allSumTxW + allSumW * sumT[cent] - 2 * flippedWT);
}

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