oj.uz

Submission #436804

# Submission time Handle Problem Language Result Execution time Memory
436804 2021-06-25T00:56:23 Z edenooo Distributing Candies (IOI21_candies) C++17
29 / 100
 152 ms 12012 KB 
#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

#define INF (ll)1e18
#define ll long long

int N, Q;
ll A[200201], mn[200201], mx[200201];

vector<int> distribute_candies(vector<int> C, vector<int> L,
                                    vector<int> R, vector<int> V) {
    N = C.size(); Q = L.size();
    ll sum = 0;
    A[0] = 0;
    for(int i=0; i<Q; i++)
    {
        sum += V[i];
        A[i+1] = sum;
    }
    mn[Q+1] = INF, mx[Q+1] = -INF; //
    for(int i=Q; i>=0; i--)
    {
        mn[i] = min(mn[i+1], A[i]);
        mx[i] = max(mx[i+1], A[i]);
    }

    vector<int> res(N);
    for(int i=0; i<N; i++)
    {
        // 합이 C[i] 이상인 최단 suffix 찾기
        int lo = -1, hi = Q; // lo : 가능, hi : 불가능
        for(int j=0; j<18; j++)
        {
            int mid = lo+hi>>1;
            if (mid == -1) break;
            else if (mx[mid]-mn[mid] >= C[i]) lo = mid;
            else hi = mid;
        }
        if (lo == -1) res[i] = A[Q]-mn[0];
        else if (mn[lo] != mn[lo+1]) res[i] = C[i]-(mx[lo]-A[Q]);
        else res[i] = A[Q]-mn[lo];
    }
    return res;
}

// int main() {}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:36:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             int mid = lo+hi>>1;
      |                       ~~^~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 11968 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 204 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 62 ms 9688 KB Output is correct
4 Correct 86 ms 2864 KB Output is correct
5 Correct 134 ms 12012 KB Output is correct
6 Correct 132 ms 11976 KB Output is correct
7 Correct 137 ms 12008 KB Output is correct
8 Correct 134 ms 12008 KB Output is correct
9 Correct 143 ms 11964 KB Output is correct

Subtask #5
0 / 33.0

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