oj.uz

Submission #446437

# Submission time Handle Problem Language Result Execution time Memory
446437 2021-07-21T23:17:28 Z luciocf Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 7648 KB 
#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

struct Range
{
    int l, r, v;

    bool operator < (const Range &o) const
    {
        if (l == o.l)
        {
            if (r == o.r) return v < o.v;
            return r < o.r;
        }

        return l < o.l;
    }
};

multiset<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 (r <= it->r)
        {
            if (it->l != l) range.insert({it->l, l-1, it->v});

            range.insert({l, r, value(it->v, v)});

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

            range.erase(it);

            continue;
        }

        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;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 0 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 Execution timed out 5098 ms 7648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 5079 ms 5232 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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