oj.uz

Submission #774574

# Submission time Handle Problem Language Result Execution time Memory
774574 2023-07-05T20:10:02 Z dxz05 Distributing Candies (IOI21_candies) C++17
0 / 100
 101 ms 16880 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);

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

        long long Y = p[j];
        if (V[j] < 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 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 16880 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
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 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -