oj.uz

Submission #814305

# Submission time Handle Problem Language Result Execution time Memory
814305 2023-08-08T06:45:34 Z LittleCube Distributing Candies (IOI21_candies) C++17
29 / 100
 124 ms 11996 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 0 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 117 ms 11268 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 47 ms 6392 KB Output is correct
4 Correct 69 ms 6588 KB Output is correct
5 Correct 108 ms 11904 KB Output is correct
6 Correct 111 ms 11856 KB Output is correct
7 Correct 124 ms 11996 KB Output is correct
8 Correct 113 ms 11808 KB Output is correct
9 Correct 93 ms 11912 KB Output is correct

Subtask #5
0 / 33.0

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