oj.uz

Submission #682425

# Submission time Handle Problem Language Result Execution time Memory
682425 2023-01-16T08:35:04 Z MilosMilutinovic Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1896 ms 130056 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 200005;
const long long inf = (long long) 1.01e12;

int root, ls[MAX * 60], rs[MAX * 60], tsz;
long long sum[MAX * 60];
long long tot[MAX];
long long f[MAX];
multiset<long long> c;

void modify(int& v, long long l, long long r, long long i, int x) {
  if (!v) {
    v = ++tsz;
  }
  sum[v] += x * i;
  if (l == r) {
    return;
  }
  long long mid = l + r >> 1;
  if (i <= mid) {
    modify(ls[v], l, mid, i, x);
  } else {
    modify(rs[v], mid + 1, r, i, x);
  }
}

long long query(int v, long long l, long long r, long long ql, long long qr) {
  if (l > qr || r < ql || l > r) {
    return 0LL;
  }
  if (ql <= l && r <= qr) {
    return sum[v];
  }
  long long mid = l + r >> 1;
  return query(ls[v], l, mid, ql, qr) + query(rs[v], mid + 1, r, ql, qr);
}

long long walk(int v, long long l, long long r, long long s) {
  if (l == r) {
    return s - sum[v] == 0 ? l : l - 1;
  }
  long long mid = l + r >> 1;
  if (ls[v] && s < sum[ls[v]]) {
    return walk(ls[v], l, mid, s);
  } else {
    return walk(rs[v], mid + 1, r, s - sum[ls[v]]);
  }
}

bool Check() {
  if (query(root, 1, inf, 1, inf) == 0) {
    return true;
  }
  if (query(root, 1, inf, 1, 1) == 0) {
    return false;
  }
  long long p = 1;
  while (true) {
    long long s = query(root, 1, inf, 1, p);
    auto it = c.lower_bound(s + 2);
    long long nxt = (it == c.end() ? inf : *it);
    if (nxt == inf) {
      break;
    }
    if (query(root, 1, inf, 1, nxt - 1) + 1 < nxt) {
      return false;
    }
    p = nxt;
  }
  return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
  for (int i = 0; i < coinsCount; i++) {
    modify(root, 1, inf, coins[i], +1);
    c.insert(coins[i]);
  }
  return Check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
  if (event == -1) {
    for (int i = 0; i < coinsCount; i++) {
      assert(query(root, 1, inf, coins[i], coins[i]) > 0);
      modify(root, 1, inf, coins[i], -1);
      c.erase(c.find(coins[i]));
    }
  } else {
    for (int i = 0; i < coinsCount; i++) {
      modify(root, 1, inf, coins[i], +1);
      c.insert(coins[i]);
    }
  }
  return Check();
}

Compilation message

happiness.cpp: In function 'void modify(int&, long long int, long long int, long long int, int)':
happiness.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   long long mid = l + r >> 1;
      |                   ~~^~~
happiness.cpp: In function 'long long int query(int, long long int, long long int, long long int, long long int)':
happiness.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   long long mid = l + r >> 1;
      |                   ~~^~~
happiness.cpp: In function 'long long int walk(int, long long int, long long int, long long int)':
happiness.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   long long mid = l + r >> 1;
      |                   ~~^~~
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 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 24 ms 5368 KB Output is correct
9 Correct 24 ms 5332 KB Output is correct
10 Correct 31 ms 5204 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 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 769 ms 17180 KB Output is correct
7 Correct 739 ms 16836 KB Output is correct
8 Correct 854 ms 17000 KB Output is correct
9 Correct 1260 ms 20276 KB Output is correct
10 Correct 1271 ms 24248 KB Output is correct
11 Correct 273 ms 20812 KB Output is correct
12 Correct 272 ms 20796 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 1 ms 348 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 872 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 24 ms 5368 KB Output is correct
9 Correct 24 ms 5332 KB Output is correct
10 Correct 31 ms 5204 KB Output is correct
11 Correct 769 ms 17180 KB Output is correct
12 Correct 739 ms 16836 KB Output is correct
13 Correct 854 ms 17000 KB Output is correct
14 Correct 1260 ms 20276 KB Output is correct
15 Correct 1271 ms 24248 KB Output is correct
16 Correct 273 ms 20812 KB Output is correct
17 Correct 272 ms 20796 KB Output is correct
18 Correct 1442 ms 79132 KB Output is correct
19 Correct 1509 ms 82064 KB Output is correct
20 Correct 1896 ms 130056 KB Output is correct
21 Correct 1050 ms 70452 KB Output is correct
22 Correct 324 ms 20856 KB Output is correct
23 Correct 311 ms 20928 KB Output is correct
24 Correct 1424 ms 76000 KB Output is correct