oj.uz

Submission #435816

# Submission time Handle Problem Language Result Execution time Memory
435816 2021-06-23T18:31:35 Z tutis Distributing Candies (IOI21_candies) C++17
29 / 100
 128 ms 7352 KB 
#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;
}

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: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.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 123 ms 7348 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 64 ms 4952 KB Output is correct
4 Correct 72 ms 2788 KB Output is correct
5 Correct 122 ms 7352 KB Output is correct
6 Correct 122 ms 7264 KB Output is correct
7 Correct 128 ms 7260 KB Output is correct
8 Correct 118 ms 7260 KB Output is correct
9 Correct 124 ms 7348 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 -