Submission #1248523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248523		adrilen	Distributing Candies (IOI21_candies)	C++17	0 / 100	49 ms	11440 KiB

candies

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

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int>l, std::vector<int> r, std::vector<int> v) {
    
    vector<ll> prefix;
    prefix.push_back(v.front());
    int n = v.size();
    for (int i = 1; i < n; i++) prefix.push_back(v[i] + prefix.back());

    vector<ll>min_prefix(n), max_prefix(n);
    min_prefix[n - 1] = max_prefix[n - 1] = prefix.back();
    for (int i = n - 2; i >= 0; i--)
    {
        min_prefix[i] = min(min_prefix[i+1], prefix[i]);
        max_prefix[i] = max(max_prefix[i + 1], prefix[i]);
    }
    
    vector<int> output;
    for (int i = 0; i < n; i++)
    {
        int lower = 0, upper = n - 1, mid;
        while (lower < upper)
        {
            mid = (lower + upper + 1) / 2;

            if (max_prefix[mid] - min_prefix[i] >= c[i]) lower = mid;
            else upper = mid - 1;
        }

        if (max_prefix[lower] == max_prefix[lower + 1])
        {
            output[i] = c[i] - (max_prefix[lower] - prefix.back());
        } else {
            output[i] = prefix.back() -  min_prefix[lower];
        }
    }
    return output;
}

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