제출 #1243659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243659		Arturgo	Distributing Candies (IOI21_candies)	C++20	100 / 100	472 ms	30308 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];
}

int prem_sup_borne(int borne, int n = 1, int sz = (1 << 18), long long shift = 0, long long mini = 1e18, long long maxi = -1e18) {
    if(sz == 1) {
        return 0;
    }
    shift += decs[n];
    long long maxim = max(maxi, maxs[2 * n + 1] + decs[2 * n + 1] + shift);
    long long minim = min(mini, mins[2 * n + 1] + decs[2 * n + 1] + shift);
    if(maxim - minim >= borne) return sz / 2 + prem_sup_borne(borne, 2 * n + 1, sz / 2, shift, mini, maxi);
    return prem_sup_borne(borne, 2 * n, sz / 2, shift, minim, maxim);
}

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 premFail = prem_sup_borne(bornes[pos]);
        if(max_entre(premFail, LAST) - min_entre(premFail, 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