Cod sursa(job #3205535)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 19 februarie 2024 22:11:12
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#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;
}