Submission #590418

#	Time	Username	Problem	Language	Result	Execution time	Memory
590418		Shreyan_Paliwal	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1194 ms	380128 KiB

happiness

#include <bits/stdc++.h>
using namespace std;

#define lg long long

struct Node {
  lg    l, r, val = 0;
  Node* c[2] = { nullptr, nullptr };

  Node(lg L, lg R) : l(L), r(R) {
    c[0] = c[1] = nullptr;
    val         = 0;
  }

  void upd(lg p, lg v) {
    val += p * v;
    if (l != r) {
      lg mid = (l + r) >> 1;
      if (p >= mid + 1) {
        if (!c[1]) c[1] = new Node(mid + 1, r);
        c[1]->upd(p, v);
      } else {
        if (!c[0]) c[0] = new Node(l, mid);
        c[0]->upd(p, v);
      }
    }
  }

  lg qry(lg L, lg R) {
    if (r < L || R < l) return 0;
    if (r <= R && l >= L) return val;
    return (c[0] ? c[0]->qry(L, R) : 0) + (c[1] ? c[1]->qry(L, R) : 0);
  }
};

Node* seg;

bool works() {
  lg bp = 1, sum = seg->val;
  while (bp < sum) {
    lg nxt = seg->qry(1, bp);
    if (nxt < bp) return false;
    bp = nxt + 1;
  }
  return true;
}

bool init(int coinsCount, lg maxCoinSize, lg coins[]) {
  seg = new Node(1, maxCoinSize);
  for (int i = 0; i < coinsCount; i++) seg->upd(coins[i], 1);
  return works();
}

bool is_happy(int event, int coinsCount, lg coins[]) {
  for (int i = 0; i < coinsCount; i++) seg->upd(coins[i], event);
  return works();
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40