Submission #446436

#	Time	Username	Problem	Language	Result	Execution time	Memory
446436		luciocf	Distributing Candies (IOI21_candies)	C++17	0 / 100	100 ms	13020 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

struct Range
{
    int l, r, v;

    bool operator < (const Range &o) const
    {
        l < o.l;
    }
};

set<Range> range;

int C;

int value(int v, int add)
{
    if (add + v > C) return C;
    if (add + v < 0) return 0;
    return add+v;
}

vector<int> distribute_candies(vector<int> c, vector<int> L, vector<int> R, vector<int> V)
{
    C = c[0];
    int n = c.size(), q = L.size();

    range.insert({1, n, 0});

    for (int i = 0; i < q; i++)
    {
        int l = L[i]+1, r = R[i]+1, v = V[i];

        auto it = range.upper_bound({l, n+1, n+1});
        it--;

        if (it->l != l) range.insert({it->l, l-1, it->v});
        range.insert({l, it->r, value(it->v, v)});
        range.erase(it);

        for (auto it = range.upper_bound({l, n+1, n+1}); it != range.end() && it->r <= r; )
        {
            Range k = {it->l, it->r, value(it->v, v)};
            it = range.erase(it);
            range.insert(k);
        }

        it = range.upper_bound({r, n+1, n+1});
        it--;

        range.insert({it->l, r, value(it->v, v)});
        if (r != it->r) range.insert({r+1, it->r, it->v});
        range.erase(it);
    }

    vector<int> ans;

    for (int i = 1; i <= n; i++)
    {
        auto it = range.upper_bound({i, n+1, n+1});
        it--;

        ans.push_back(it->v);
    }

    return ans;
}

Compilation message (stderr)

candies.cpp: In member function 'bool Range::operator<(const Range&) const':
candies.cpp:12:11: warning: statement has no effect [-Wunused-value]
   12 |         l < o.l;
      |         ~~^~~~~
candies.cpp:13:5: warning: no return statement in function returning non-void [-Wreturn-type]
   13 |     }
      |     ^

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