Submission #1243652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243652		Arturgo	Distributing Candies (IOI21_candies)	C++20	100 / 100	1762 ms	30408 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

long long mins[(1 << 19)];
long long maxs[(1 << 19)];
long long decs[(1 << 19)];

void ajoute(int deb, int fin, long long val, int n = 1, int d = 0, int f = (1 << 18)) {
    if(deb >= f || fin <= d) return;
    if(deb <= d && f <= fin) {
        decs[n] += val;
        return;
    }

    int m = (d + f) / 2;
    ajoute(deb, fin, val, 2 * n, d, m);
    ajoute(deb, fin, val, 2 * n + 1, m, f);
    mins[n] = min(mins[2 * n] + decs[2 * n], mins[2 * n + 1] + decs[2 * n + 1]);
    maxs[n] = max(maxs[2 * n] + decs[2 * n], maxs[2 * n + 1] + decs[2 * n + 1]);
}

long long min_entre(int deb, int fin, int n = 1, int d = 0, int f = (1 << 18)) {
    if(deb >= f || fin <= d) return 1e18;
    if(deb <= d && f <= fin) {
        return mins[n] + decs[n];
    }
    int m = (d + f) / 2;
    return min(min_entre(deb, fin, 2 * n, d, m), min_entre(deb, fin, 2 * n + 1, m, f)) + decs[n];
}

long long max_entre(int deb, int fin, int n = 1, int d = 0, int f = (1 << 18)) {
    if(deb >= f || fin <= d) return -1e18;
    if(deb <= d && f <= fin) {
        return maxs[n] + decs[n];
    }
    int m = (d + f) / 2;
    return max(max_entre(deb, fin, 2 * n, d, m), max_entre(deb, fin, 2 * n + 1, m, f)) + decs[n];
}

vector<int> distribute_candies(vector<int> bornes, vector<int> debs, vector<int> fins, vector<int> ajouts) {
    vector<int> final(bornes.size(), -1);

    vector<vector<int>> intersDeb(bornes.size());
    vector<vector<int>> intersFin(bornes.size());

    for(int iReq = 0;iReq < (int)ajouts.size();iReq++) {
        intersDeb[debs[iReq]].push_back(iReq);
        intersFin[fins[iReq]].push_back(iReq);
    }

    int LAST = ajouts.size() + 2;
    long long total = 0;

    for(int pos = 0;pos < (int)bornes.size();pos++) {
        for(int iReq : intersDeb[pos]) {
            ajoute(iReq + 1, (1 << 18), ajouts[iReq]);
            total += ajouts[iReq];
        }

        int deb = 0, fin = LAST + 1;
        while(fin - deb > 1) {
            int mil = (deb + fin) / 2;
            if(max_entre(mil, LAST) - min_entre(mil, LAST) >= bornes[pos]) {
                deb = mil;
            } else {
                fin = mil;
            }
        }
        int premFail = deb;
        if(max_entre(0, LAST) - min_entre(0, LAST) < bornes[pos]) premFail = LAST;

        if(max_entre(premFail, LAST) == max_entre(premFail, premFail + 1) || premFail == LAST) {
            if(premFail == LAST) premFail = 0;

            long long minApres = min_entre(premFail, LAST + 1);
            final[pos] = total - minApres;
        } else {
            long long maxApres = max_entre(premFail, LAST + 1);
            final[pos] = bornes[pos] - (maxApres - total);
        }

        for(int iReq : intersFin[pos]) {
            ajoute(iReq + 1, (1 << 18), -ajouts[iReq]);
            total -= ajouts[iReq];
        }
    }

    return final;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33