Submission #814297

#	Time	Username	Problem	Language	Result	Execution time	Memory
814297		LittleCube	Distributing Candies (IOI21_candies)	C++17	0 / 100	123 ms	11904 KiB

candies

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

// find last reset,
// for larger c, the suffix does not reset so only compute prefix
// for smaller c, the prefix always reset so only compute suffix

namespace
{
    int n, q;
    vector<int> c, v, res, ord, ans;
    void solve(int l, int r, int ql, int qr, ll suf, ll reset)
    {
        if (r < l)
            return;
        ll sum = 0;

        // calculate mid
        int mid = (l + r) / 2, cur = reset * c[mid], last = ql - 1, type = reset;
        // cerr << l << ' ' << mid << ' ' << r << ' ' << ql << ' ' << qr << ' ' << reset << '\n';
        for (int i = ql; i <= qr; i++)
        {
            int nxt = cur + v[i];
            sum += v[i];
            if (nxt > c[mid])
                last = i, type = 1, nxt = c[mid], sum = 0;
            else if (nxt < 0)
                last = i, type = 0, nxt = 0, sum = 0;
            cur = nxt;
        }
        res[mid] = cur + suf;
        solve(l, mid - 1, last + 1, qr, suf, type);
        solve(mid + 1, r, ql, last, sum + suf, reset);
    }
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v)
{

    n = c.size(), q = l.size();
    ::c = c, ::v = v;
    res.resize(n);
    ans.resize(n);
    ord.resize(n);
    for (int i = 0; i < n; i++)
        ord[i] = i;
    sort(ord.begin(), ord.end(), [&](int i, int j)
         { return c[i] < c[j]; });
    sort(c.begin(), c.end());
    solve(0, n - 1, 0, q - 1, 0, 0);
    for (int i = 0; i < n; i++)
        ans[ord[i]] = res[i];
    return ans;
}

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