Submission #593601

#	Time	Username	Problem	Language	Result	Execution time	Memory
593601		PiejanVDC	Distributing Candies (IOI21_candies)	C++17	0 / 100	105 ms	12728 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) {

    const int n = (int)c.size();
    const int m = (int)l.size();

    vector<int>value(m+5);
    value[0] = 0;
    
    for(int i = 1 ; i <= m ; i++)
        value[i] = value[i-1] + v[i-1];

    vector<int>suff_max(m+1), suff_min(m+1);
    suff_max[m] = INT_MIN;
    suff_min[m] = INT_MAX;

    for(int i = m-1 ; i >= 0 ; i--) {
        suff_max[i] = max(suff_max[i+1], value[i+1]);
        suff_min[i] = min(suff_min[i+1], value[i+1]);
    }

    vector<int>ans(n);

    for(int i = 0 ; i < n ; i++) {

        int p = m;
        int l = 0, r = m-1;

        while(l <= r) {
            int mid = (l+r)/2;
            if(suff_max[mid] - suff_min[mid] > c[i]) {
                l = mid+1, p = mid;
            } else {
                r = mid-1;
            }
        }

        if(value[p+1] == suff_min[p]) { // smaller side 
            ans[i] = c[i] - (suff_max[p] - value[m]);
        } else {
            ans[i] = value[m] - suff_min[p];
        }

    }

    return ans;
}

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