Submission #383133

#	Time	Username	Problem	Language	Result	Execution time	Memory
383133		JerryLiu06	Happiness (Balkan15_HAPPINESS)	C++11	100 / 100	1572 ms	322284 KiB

happiness

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node { ll sum = 0, tl, tr; int l = -1, r = -1; };

int timer = 2; Node tree[10000000];

void update(int x, ll pos, ll val) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum += val; return ; }

    if (pos <= mid) { if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = mid; } update(tree[x].l, pos, val); }
    if (pos > mid) { if (tree[x].r == -1) { tree[x].r = timer++; tree[tree[x].r].tl = mid + 1; tree[tree[x].r].tr = tree[x].tr; } update(tree[x].r, pos, val); }
        
    tree[x].sum = ((tree[x].l == -1) ? 0 : tree[tree[x].l].sum) + ((tree[x].r == -1) ? 0 : tree[tree[x].r].sum);
}
ll query(int x, ll l, ll r) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;

    return ((tree[x].l == -1) ? 0 : query(tree[x].l, l, r)) + ((tree[x].r == -1) ? 0 : query(tree[x].r, l, r));
}
bool valid() {
    ll CUR = 1; ll TOT = tree[1].sum;

    while (CUR < TOT) { ll PREF = query(1, 1, CUR); if (CUR <= PREF) CUR = PREF + 1; else return false; } return true;
}
bool init(int countCoins, ll maxCoinSize, ll coins[]) { 
    tree[1].tl = 1; tree[1].tr = maxCoinSize;

    for (int i = 0; i < countCoins; i++) update(1, coins[i], coins[i]); return valid();
}
bool is_happy(int event, int countCoins, ll coins[]) {
    for (int i = 0; i < countCoins; i++) update(1, coins[i], event * coins[i]); return valid();
}

Compilation message (stderr)

happiness.cpp: In function 'void update(int, ll, ll)':
happiness.cpp:12:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   12 |     if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum += val; return ; }
      |     ^~
happiness.cpp:12:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   12 |     if (tree[x].tl > pos || tree[x].tr < pos) return ; if (tree[x].tl == tree[x].tr) { tree[x].sum += val; return ; }
      |                                                        ^~
happiness.cpp: In function 'll query(int, ll, ll)':
happiness.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   20 |     if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;
      |     ^~
happiness.cpp:20:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |     if (tree[x].tl > r || tree[x].tr < l) return 0; if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;
      |                                                     ^~
happiness.cpp:19:34: warning: unused variable 'mid' [-Wunused-variable]
   19 | ll query(int x, ll l, ll r) { ll mid = (tree[x].tl + tree[x].tr) / 2;
      |                                  ^~~
happiness.cpp: In function 'bool init(int, ll, ll*)':
happiness.cpp:32:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   32 |     for (int i = 0; i < countCoins; i++) update(1, coins[i], coins[i]); return valid();
      |     ^~~
happiness.cpp:32:73: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   32 |     for (int i = 0; i < countCoins; i++) update(1, coins[i], coins[i]); return valid();
      |                                                                         ^~~~~~
happiness.cpp: In function 'bool is_happy(int, int, ll*)':
happiness.cpp:35:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   35 |     for (int i = 0; i < countCoins; i++) update(1, coins[i], event * coins[i]); return valid();
      |     ^~~
happiness.cpp:35:81: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   35 |     for (int i = 0; i < countCoins; i++) update(1, coins[i], event * coins[i]); return valid();
      |                                                                                 ^~~~~~
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