oj.uz

Submission #590418

# Submission time Handle Problem Language Result Execution time Memory
590418 2022-07-05T23:01:20 Z Shreyan_Paliwal Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1194 ms 380128 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1732 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 23 ms 14028 KB Output is correct
9 Correct 24 ms 14152 KB Output is correct
10 Correct 21 ms 13712 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 333 ms 37528 KB Output is correct
7 Correct 338 ms 37056 KB Output is correct
8 Correct 369 ms 37444 KB Output is correct
9 Correct 514 ms 48716 KB Output is correct
10 Correct 501 ms 52684 KB Output is correct
11 Correct 132 ms 37060 KB Output is correct
12 Correct 131 ms 37136 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1732 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 23 ms 14028 KB Output is correct
9 Correct 24 ms 14152 KB Output is correct
10 Correct 21 ms 13712 KB Output is correct
11 Correct 333 ms 37528 KB Output is correct
12 Correct 338 ms 37056 KB Output is correct
13 Correct 369 ms 37444 KB Output is correct
14 Correct 514 ms 48716 KB Output is correct
15 Correct 501 ms 52684 KB Output is correct
16 Correct 132 ms 37060 KB Output is correct
17 Correct 131 ms 37136 KB Output is correct
18 Correct 789 ms 225832 KB Output is correct
19 Correct 869 ms 234656 KB Output is correct
20 Correct 1194 ms 380128 KB Output is correct
21 Correct 639 ms 199092 KB Output is correct
22 Correct 186 ms 39060 KB Output is correct
23 Correct 166 ms 39628 KB Output is correct
24 Correct 800 ms 216716 KB Output is correct