oj.uz

답안 #775535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
775535 2023-07-06T13:32:05 Z dxz05 사탕 분배 (IOI21_candies) C++17
29 / 100
 104 ms 12308 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 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 12212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 57 ms 9920 KB Output is correct
4 Correct 47 ms 3100 KB Output is correct
5 Correct 88 ms 12212 KB Output is correct
6 Correct 98 ms 12292 KB Output is correct
7 Correct 104 ms 12308 KB Output is correct
8 Correct 85 ms 12216 KB Output is correct
9 Correct 85 ms 12212 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -