oj.uz

Submission #682412

# Submission time Handle Problem Language Result Execution time Memory
682412 2023-01-16T08:13:48 Z MilosMilutinovic Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 128956 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 (ql <= l && r <= qr) {
    return sum[v];
  }
  if (l > qr || r < ql || l > r) {
    return 0LL;
  }
  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) {
    if (query(root, 1, inf, p + 1, inf) == 0) {
      break;
    }
    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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 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 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 29 ms 5364 KB Output is correct
9 Correct 28 ms 5324 KB Output is correct
10 Correct 25 ms 5252 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 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 1006 ms 17044 KB Output is correct
7 Correct 963 ms 16944 KB Output is correct
8 Correct 1083 ms 17064 KB Output is correct
9 Correct 1378 ms 20348 KB Output is correct
10 Correct 1444 ms 24204 KB Output is correct
11 Correct 298 ms 20772 KB Output is correct
12 Correct 276 ms 20796 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 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 852 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 29 ms 5364 KB Output is correct
9 Correct 28 ms 5324 KB Output is correct
10 Correct 25 ms 5252 KB Output is correct
11 Correct 1006 ms 17044 KB Output is correct
12 Correct 963 ms 16944 KB Output is correct
13 Correct 1083 ms 17064 KB Output is correct
14 Correct 1378 ms 20348 KB Output is correct
15 Correct 1444 ms 24204 KB Output is correct
16 Correct 298 ms 20772 KB Output is correct
17 Correct 276 ms 20796 KB Output is correct
18 Correct 1783 ms 79872 KB Output is correct
19 Correct 1839 ms 87520 KB Output is correct
20 Execution timed out 2013 ms 128956 KB Time limit exceeded
21 Halted 0 ms 0 KB -