제출 #435816

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435816		tutis	사탕 분배 (IOI21_candies)	C++17	29 / 100	128 ms	7352 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> s(n, 0);
    int q = l.size();
    vector<pair<ll, ll>>D = {{0ll, (ll)1e16 + 1}};
    for (int i = 0; i < q; i++)
    {
        while (v[i] != 0)
        {
            if (v[i] > 0)
            {
                ll x = D.back().second - D.back().first;
                if (v[i] >= x)
                {
                    v[i] -= x;
                    D.pop_back();
                }
                else
                {
                    D.back().first += v[i];
                    v[i] = 0;
                }
            }
            else
            {
                if (D.back().first != 0)
                {
                    if (-v[i] >= D.back().first)
                    {
                        v[i] += D.back().first;
                        D.back().first = 0;
                    }
                    else
                    {
                        D.push_back({0, -v[i]});
                        v[i] = 0;
                    }
                }
                else
                {
                    if (D.size() == 1)
                        v[i] = 0;
                    else
                    {
                        ll x = D[D.size() - 2].first - D.back().second;
                        if (-v[i] >= x)
                        {
                            v[i] += x;
                            D.pop_back();
                            D.back().first = 0;
                        }
                        else
                        {
                            D.back().second += -v[i];
                            v[i] = 0;
                        }
                    }
                }
            }
        }
    }
    reverse(D.begin(), D.end());
    vector<ll>S(D.size());
    S[0] = D[0].first;
    for (int i = 1; i < D.size(); i++)
        S[i] = S[i - 1] + D[i].first - D[i - 1].second;
    for (int j = 0; j < n; j++)
    {
        if (c[j] <= D[0].first)
            s[j] = c[j];
        else
        {
            int lo = 0;
            int hi = D.size() - 1;
            while (lo <= hi)
            {
                int i = (lo + hi) / 2;
                if (D[i].first <= c[j] && c[j] <= D[i].second)
                {
                    s[j] = S[i];
                    break;
                }
                if (c[j] <= D[i].first)
                    hi = i - 1;
                else
                {
                    if (c[j] <= D[i + 1].first)
                    {
                        s[j] = S[i] + (c[j] - D[i].second);
                        break;
                    }
                    lo = i + 1;
                }
            }
        }
    }
    return s;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 1; i < D.size(); i++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33