Submission #561946

#	Time	Username	Problem	Language	Result	Execution time	Memory
561946		Lucina	Distributing Candies (IOI21_candies)	C++17	0 / 100	117 ms	15940 KiB

candies

#include "candies.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int nax = 4e5 + 10;
int n, q;
int c[nax];
int64_t a[nax];
int v[nax];
int l[nax];
int r[nax];
int link_to[nax];
int64_t suf_mx[nax];
int64_t suf_mn[nax];




void get_local_max_min_link() {
    suf_mn[q] = suf_mx[q] = a[q];

    for (int i = q - 1 ; i >= 0 ; -- i) {

        suf_mn[i] = min(suf_mn[i + 1], a[i]);
        suf_mx[i] = max(suf_mx[i + 1], a[i]);
    }
    pair <int64_t, int> mn = make_pair(a[q], q);
    pair <int64_t, int> mx = make_pair(a[q], q);

    for (int i = q - 1 ; i >= 0 ; -- i) {
        int prv_mn = mn.second, prv_mx = mx.second;
        if (a[i] <= mx.first) {
            link_to[i] = mx.second;
        } else link_to[i] = prv_mn, mx = make_pair(a[i], i);
        if (a[i] >= mn.first) {
            link_to[i] = mn.second;
        } else link_to[i] = prv_mx, mn = make_pair(a[i], i);
    }
}


vector <int> solve() {
    for (int i = 1 ; i <= q ; ++ i) {
        a[i] += a[i - 1];
        a[i] += v[i];
    }
    get_local_max_min_link();


    vector <int> ans(n);

    for (int i = 1 ; i <= n ; ++ i) {
        int k = c[i];
        int l = 0, r = q, ans1 = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (suf_mx[mid] - suf_mn[mid] >= k) {
                ans1 = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        if (ans1 == -1) {
            ans[i - 1] = a[q];
        } else {
            int lst_ind = link_to[ans1];
            assert(abs(a[lst_ind] - a[ans1]) >= k);
            int64_t x = a[q] - a[lst_ind];
            if (a[ans1] == suf_mn[ans1]) ans[i - 1] = k + x;
            else ans[i - 1] = x;
        }
    }
    return ans;
}


std::vector<int> distribute_candies(std::vector<int> _c, std::vector<int> _l,
                                    std::vector<int> _r, std::vector<int> _v) {
    n = _c.size();
    q = _v.size();

//    auto brute = [&]()->vector<int> {
//        vector <int> ans(n, 0);
//
//        for (int i = 0 ; i < _l.size() ; ++ i) {
//            for (int j = _l[i] ; j <= _r[i] ; ++ j) {
//                ans[j] = max(0, min(_c[j], ans[j] + _v[i]));
//            }
//        }
//        return ans;
//    };
    for (int i = 0 ; i < q ; ++ i) {
        v[i + 1] = _v[i];
        l[i + 1] = _l[i] + 1;
        r[i + 1] = _r[i] + 1;
    }
    for (int i = 0 ; i < n ; ++ i) {
        c[i + 1] = _c[i];
    }
    return solve();
}


/*
int main() {

}
*/

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> solve()':
candies.cpp:57:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |             int mid = l + r >> 1;
      |                       ~~^~~

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