oj.uz

Submission #814297

# Submission time Handle Problem Language Result Execution time Memory
814297 2023-08-08T06:43:25 Z LittleCube Distributing Candies (IOI21_candies) C++17
0 / 100
 123 ms 11904 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 11904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -