Pagini recente » Cod sursa (job #2154120) | Cod sursa (job #2297177) | Cod sursa (job #1541431) | Cod sursa (job #7855) | Cod sursa (job #3205535)
#include <bits/stdc++.h>
#define L 1000005
#define MAX_PRICE 1000001
#define lsb(x) (x & (-x))
using namespace std;
long long aib1[L], aib2[L];
priority_queue <pair <long long, long long>> pq;
vector <pair <int, int>> sold;
void update1(long long pos, long long val) {
for (; pos <= MAX_PRICE; pos += lsb(pos))
aib1[pos] += val;
}
void update2(long long pos, long long val) {
for (; pos <= MAX_PRICE; pos += lsb(pos))
aib2[pos] += val;
}
long long query1(long long pos) {
long long r = 0;
for (; pos; pos -= lsb(pos))
r += aib1[pos];
return r;
}
long long query2(long long pos) {
long long r = 0;
for (; pos; pos -= lsb(pos))
r += aib2[pos];
return r;
}
int main() {
string str;
while (cin >> str) {
long long n, p;
cin >> n >> p;
if (str[0] == 'A') {
update1(p, n);
update2(p, n * p);
pq.push({-p, n});
}
else {
long long le = 0, ri = MAX_PRICE, best = MAX_PRICE + 1;
while (le <= ri) {
long long mid = (le + ri) / 2;
if (query2(mid) <= p) {
le = mid + 1;
best = mid;
}
else
ri = mid - 1;
}
le = 0, ri = MAX_PRICE;
long long afterBest = MAX_PRICE + 2;
while (le <= ri) {
long long mid = (le + ri) / 2;
if (query2(mid) > query2(best)) {
ri = mid - 1;
afterBest = mid;
}
else
le = mid + 1;
}
if (!(afterBest * (n - query1(best)) <= p - query2(best) && n - query1(best) <= query1(afterBest) - query1(afterBest - 1))) {
cout << "UNHAPPY\n";
continue;
}
long long s = 0, val = 0;
sold.clear();
while (true) {
long long topPrice = -pq.top().first, quant = 0;
while (!pq.empty() && -pq.top().first == topPrice) {
quant += pq.top().second;
pq.pop();
}
sold.push_back({-topPrice, quant});
if (s + quant < n) {
s += quant;
val += topPrice * quant;
}
else
break;
}
pq.push({sold.back().first, sold.back().second - (n - s)});
sold.back() = {sold.back().first, n - s};
for (int i = 0; i < (int)sold.size(); i++) {
update1(-sold[i].first, -sold[i].second);
update2(-sold[i].first, sold[i].first * sold[i].second);
}
cout << "HAPPY\n";
}
}
return 0;
}