oj.uz

Submission #73238

# Submission time Handle Problem Language Result Execution time Memory
73238 2018-08-28T05:45:20 Z 강태규(#2268) Happiness (Balkan15_HAPPINESS) C++11
100 / 100
 1393 ms 396328 KB 
#include "happiness.h"

typedef long long llong;

llong mx;
struct node {
    int l, r;
    llong sum;
    node() : l(-1), r(-1), sum(0) {}
} ns[42 * 600000];

int _alloc() {
    static int tp = 0;
    return tp++;
}

void update(int &i, llong s, llong e, llong x, llong v) {
    if (i == -1) i = _alloc();
    ns[i].sum += v;
    if (s == e) return;
    llong m = (s + e) / 2;
    if (x <= m) update(ns[i].l, s, m, x, v);
    else update(ns[i].r, m + 1, e, x, v);
}

llong query(int &i, llong s, llong e, llong x) {
    if (i == -1) return 0;
    if (x < s) return 0;
    if (e <= x) return ns[i].sum;
    llong m = (s + e) / 2;
    return query(ns[i].l, s, m, x) + query(ns[i].r, m + 1, e, x);
}

int rt;
bool check() {
    llong sum = 0, pr = -1;
    while (pr != sum) sum = query(rt, 1, mx, (pr = sum) + 1);
    return sum == ns[rt].sum;
}

bool init(int coinsCount, llong maxCoinSize, llong coins[]) {
    rt = _alloc();
    mx = maxCoinSize;
    for (int i = 0; i < coinsCount; ++i)
        update(rt, 1, mx, coins[i], coins[i]);
    return check();
}
bool is_happy(int event, int coinsCount, llong coins[]) {
    for (int i = 0; i < coinsCount; ++i)
        update(rt, 1, mx, coins[i], event * coins[i]);
    return check();
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:14:9: warning: unused variable 'd' [-Wunused-variable]
  int i, d;
         ^
grader.cpp:15:12: warning: unused variable 'max_code' [-Wunused-variable]
  long long max_code;
            ^~~~~~~~
grader.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~
grader.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &coins[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~
grader.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
grader.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &ck, &c);
   ~~~~~^~~~~~~~~~~~~~~~~
grader.cpp:28:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &A[j]);
    ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 394872 KB Output is correct
2 Correct 308 ms 394872 KB Output is correct
3 Correct 304 ms 394908 KB Output is correct
4 Correct 295 ms 394908 KB Output is correct
5 Correct 297 ms 394956 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 394956 KB Output is correct
2 Correct 293 ms 395076 KB Output is correct
3 Correct 307 ms 395076 KB Output is correct
4 Correct 310 ms 395084 KB Output is correct
5 Correct 302 ms 395100 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 396052 KB Output is correct
2 Correct 617 ms 396052 KB Output is correct
3 Correct 665 ms 396100 KB Output is correct
4 Correct 833 ms 396160 KB Output is correct
5 Correct 801 ms 396328 KB Output is correct
6 Correct 440 ms 396328 KB Output is correct
7 Correct 446 ms 396328 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 396328 KB Output is correct
2 Correct 1118 ms 396328 KB Output is correct
3 Correct 1393 ms 396328 KB Output is correct
4 Correct 873 ms 396328 KB Output is correct
5 Correct 513 ms 396328 KB Output is correct
6 Correct 515 ms 396328 KB Output is correct
7 Correct 1061 ms 396328 KB Output is correct