oj.uz

Submission #839569

# Submission time Handle Problem Language Result Execution time Memory
839569 2023-08-30T08:59:46 Z model_code Truck Driver (IOI23_deliveries) C++17
29 / 100
 279 ms 27852 KB 
// 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7708 KB Output is correct
2 Correct 84 ms 7468 KB Output is correct
3 Correct 92 ms 7704 KB Output is correct
4 Correct 73 ms 7568 KB Output is correct
5 Correct 78 ms 7724 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '2247916'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7708 KB Output is correct
2 Correct 84 ms 7468 KB Output is correct
3 Correct 92 ms 7704 KB Output is correct
4 Correct 73 ms 7568 KB Output is correct
5 Correct 78 ms 7724 KB Output is correct
6 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '45306', found: '274830'
7 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7708 KB Output is correct
2 Correct 84 ms 7468 KB Output is correct
3 Correct 92 ms 7704 KB Output is correct
4 Correct 73 ms 7568 KB Output is correct
5 Correct 78 ms 7724 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 21 ms 2928 KB Output is correct
9 Correct 227 ms 26064 KB Output is correct
10 Correct 216 ms 26068 KB Output is correct
11 Correct 241 ms 26124 KB Output is correct
12 Correct 279 ms 27852 KB Output is correct
13 Correct 254 ms 27848 KB Output is correct
14 Correct 183 ms 26068 KB Output is correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 7708 KB Output is correct
2 Correct 84 ms 7468 KB Output is correct
3 Correct 92 ms 7704 KB Output is correct
4 Correct 73 ms 7568 KB Output is correct
5 Correct 78 ms 7724 KB Output is correct
6 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '2247916'
7 Halted 0 ms 0 KB -