Submission #383128

#	Time	Username	Problem	Language	Result	Execution time	Memory
383128		JerryLiu06	Happiness (Balkan15_HAPPINESS)	C++11	60 / 100	1611 ms	514384 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[8000000];

void pushdown(int x) { ll mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = 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; }
}
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 ; }

    pushdown(x); update(tree[x].l, pos, val); update(tree[x].r, pos, val); tree[x].sum = tree[tree[x].l].sum + 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;

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