Submission #775535

#	Time	Username	Problem	Language	Result	Execution time	Memory
775535		dxz05	Distributing Candies (IOI21_candies)	C++17	29 / 100	104 ms	12308 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = (int)C.size(), q = (int)V.size();

    V.insert(V.begin(), (int) -2e9), L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    V.insert(V.begin(), (int) 2e9),  L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    q += 2;

    vector<long long> p(q);
    for (int i = 0; i < q; i++){
        p[i] = V[i];
        if (i) p[i] += p[i - 1];
    }

    vector<long long> s_min = p, s_max = p;
    for (int i = q - 2; i >= 0; i--){
        s_min[i] = min(s_min[i], s_min[i + 1]);
        s_max[i] = max(s_max[i], s_max[i + 1]);
    }

    vector<int> ans(n, 0);

    for (int i = 0; i < n; i++){
        int j = -1;
        int l = 0, r = q - 1;
        while (l <= r){
            int m = (l + r) >> 1;
            if (s_max[m] - s_min[m] >= C[i]){
                j = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        assert(j != -1);

        long long diff = s_max[j] - s_min[j] - C[i];

        long long Y = p[j];
        if (V[j + 1] > 0){ /// full
            Y += diff;
            ans[i] = p.back() - Y;
        } else { /// empty
            Y -= diff;
            ans[i] = C[i] + p.back() - Y;
        }
    }

    return ans;
}

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