Submission #436804

#	Time	Username	Problem	Language	Result	Execution time	Memory
436804		edenooo	Distributing Candies (IOI21_candies)	C++17	29 / 100	152 ms	12012 KiB

candies

#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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33