oj.uz

Submission #775529

# Submission time Handle Problem Language Result Execution time Memory
775529 2023-07-06T13:23:45 Z dxz05 Distributing Candies (IOI21_candies) C++17
29 / 100
 95 ms 16936 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
    int n = (int)C.size(), q = (int)V.size();

    V.insert(V.begin(), (int) -2e9), L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    V.insert(V.begin(), (int) 2e9),  L.insert(L.begin(), 0), R.insert(R.begin(), n - 1);
    q += 2;

    vector<long long> p(q);
    for (int i = 0; i < q; i++){
        p[i] = V[i];
        if (i) p[i] += p[i - 1];
    }

    vector<long long> s_min = p, s_max = p;
    for (int i = q - 2; i >= 0; i--){
        s_min[i] = min(s_min[i], s_min[i + 1]);
        s_max[i] = max(s_max[i], s_max[i + 1]);
    }

    vector<int> ans(n, 0);

    for (int i = 0; i < n; i++){
        int j = -1;
        int l = 0, r = q - 1;
        while (l <= r){
            int m = (l + r) >> 1;
            if (s_max[m] - s_min[m] >= C[i]){
                j = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        assert(j != -1);

        if (j == q - 1){
            if (V.back() > 0){
                ans[i] = C[i];
            } else {
                ans[i] = 0;
            }
            continue;
        }

        long long diff = s_max[j] - s_min[j] - C[i];

        long long Y = p[j];
        if (V[j + 1] > 0){ /// full
            Y += diff;
            ans[i] = p.back() - Y;
        } else { /// empty
            Y -= diff;
            ans[i] = C[i] + p.back() - Y;
        }
    }

    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 296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 16888 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 300 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 45 ms 12284 KB Output is correct
4 Correct 47 ms 4120 KB Output is correct
5 Correct 89 ms 15468 KB Output is correct
6 Correct 91 ms 16156 KB Output is correct
7 Correct 94 ms 16768 KB Output is correct
8 Correct 89 ms 15396 KB Output is correct
9 Correct 92 ms 16936 KB Output is correct

Subtask #5
0 / 33.0

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