Submission #590442

#	Time	Username	Problem	Language	Result	Execution time	Memory
590442		Shreyan_Paliwal	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1248 ms	375488 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* ML() {
    if (c[0]) return c[0];
    c[0]    = new Node;
    c[0]->l = l, c[0]->r = (l + r) >> 1;
    return c[0];
  }

  Node* MR() {
    if (c[1]) return c[1];
    c[1]    = new Node;
    c[1]->l = ((l + r) >> 1) + 1, c[1]->r = r;
    return c[1];
  }

  void upd(lg p, lg v) {
    val += p * v;
    if (l != r) {
      lg mid = (l + r) >> 1;
      if (p >= mid + 1)
        MR()->upd(p, v);
      else
        ML()->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;
  seg->l = 1;
  seg->r = 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