Submission #593698

#	Time	Username	Problem	Language	Result	Execution time	Memory
593698		PiejanVDC	Distributing Candies (IOI21_candies)	C++17	0 / 100	144 ms	16712 KiB

candies

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

void dbg(deque<long long>v) {
    for(auto z : v)
        cout << z << ' ';
    cout << '\n';
}

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<long long>v(m);

    for(int i = 0 ; i < m ; i++)
        v[i] = (long long)V[i];

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

    deque<long long>suff_max(m+2), suff_min(m+2);
    suff_max[m+1] = LLONG_MIN;
    suff_min[m+1] = LLONG_MAX;

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

    vector<int>ans(n);

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

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

        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;
            }
        }

        //cout << p << '\n';

        if(p == m+1) {
            ans[i] = value[m];
            continue;
        }

        if(value[p] == suff_min[p]) { // smaller side 
            ans[i] = max(c[i] - (suff_max[p] - value[m]), 0LL);
        } else {
            ans[i] = max(value[m] - suff_min[p], 0LL);
        }

        assert(ans[i] >= 0 && ans[i] <= c[i]);

    }

    return ans;
}

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