1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <map>
#include <stdio.h>

using Weight = long long int;
using WeightsMap = std::map<Weight, int>;

WeightsMap::const_iterator getCurrent(const WeightsMap& weightsMap, const WeightsMap& usedWeightsMap, Weight weights)
{
    auto current = weightsMap.lower_bound(weights);
    if (current == weightsMap.end())
        current--;
    while (current->first >= weights || (usedWeightsMap.count(current->first) != 0 && usedWeightsMap.at(current->first) == weightsMap.at(current->first))) {
        if (current == weightsMap.begin())
            return weightsMap.end();
        current--;
    }
    return current;
}

WeightsMap::const_iterator getNext(const WeightsMap& weightsMap, const WeightsMap& usedWeightsMap, const WeightsMap::const_iterator& current)
{
    auto next = std::next(current);
    while (next != weightsMap.end() && (usedWeightsMap.count(next->first) != 0 && usedWeightsMap.at(next->first) == weightsMap.at(next->first))) {
        next++;
    }
    return next;
}

Weight count(
    Weight s,
    const Weight k,
    const WeightsMap& weightsMap,
    const Weight totalWeightsSum,
    const int totalWeightsCount)
{
    WeightsMap usedWeightsMap;

    if (s + totalWeightsSum < k)
        return -1;
    if (s + totalWeightsSum == k)
        return totalWeightsCount;
    if (s >= k)
        return 0;
    int result = 0;
    while (s < k && !weightsMap.empty()) {
        const auto current = getCurrent(weightsMap, usedWeightsMap, s);
        if (current == weightsMap.end())
            return -1;
        Weight differenceWeight = k - s;
        const auto next = getNext(weightsMap, usedWeightsMap, current);
        if (next != weightsMap.end()) {
            differenceWeight = std::min(differenceWeight, next->first - (s) + 1);
        }
        Weight count = differenceWeight / current->first;
        if (differenceWeight % current->first != 0)
            count++;
        count = std::min(count, static_cast<Weight>(current->second));
        count = std::min(count, static_cast<Weight>(weightsMap.at(current->first) - usedWeightsMap[current->first]));

        s += count * current->first;
        result += count;
        usedWeightsMap[current->first] += count;
    }
    if (s >= k)
        return result;
    else
        return -1;
}

void changeWeight(
    WeightsMap& weightsMap,
    Weight& totalWeightsSum,
    int& totalWeightsCount,
    const Weight weight,
    const bool add)
{
    if (add) {
        weightsMap[weight]++;
        totalWeightsCount++;
        totalWeightsSum += weight;
    } else {
        weightsMap[weight]--;
        totalWeightsCount--;
        totalWeightsSum -= weight;
        if (weightsMap[weight] == 0)
            weightsMap.erase(weight);
    }
}

int main()
{
    int n, q, type, totalWeightsCount = 0;
    Weight w, s, k, totalWeightsSum = 0, result;
    WeightsMap weightsMap;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &w);
        changeWeight(weightsMap, totalWeightsSum, totalWeightsCount, w, true);
    }
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        scanf("%d", &type);
        if (type == 1) {
            scanf("%lld %lld", &s, &k);
            result = count(s, k, weightsMap, totalWeightsSum, totalWeightsCount);
            printf("%lld\n", result);
        } else {
            scanf("%lld", &w);
            changeWeight(weightsMap, totalWeightsSum, totalWeightsCount, w, type == 2);
        }
    }
    return 0;
}