Submission #383133

# Submission time Handle Problem Language Result Execution time Memory
383133 2021-03-28T21:45:09 Z JerryLiu06 Happiness (Balkan15_HAPPINESS) C++11
100 / 100
1572 ms 322284 KB
#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

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;
      |            ^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 170 ms 313452 KB Output is correct
2 Correct 175 ms 313580 KB Output is correct
3 Correct 170 ms 313580 KB Output is correct
4 Correct 167 ms 313452 KB Output is correct
5 Correct 170 ms 313452 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 170 ms 313452 KB Output is correct
2 Correct 175 ms 313580 KB Output is correct
3 Correct 170 ms 313580 KB Output is correct
4 Correct 167 ms 313452 KB Output is correct
5 Correct 170 ms 313452 KB Output is correct
6 Correct 172 ms 313484 KB Output is correct
7 Correct 169 ms 313452 KB Output is correct
8 Correct 189 ms 313580 KB Output is correct
9 Correct 194 ms 313796 KB Output is correct
10 Correct 190 ms 313452 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 170 ms 313452 KB Output is correct
2 Correct 175 ms 313580 KB Output is correct
3 Correct 170 ms 313580 KB Output is correct
4 Correct 167 ms 313452 KB Output is correct
5 Correct 170 ms 313452 KB Output is correct
6 Correct 666 ms 314724 KB Output is correct
7 Correct 647 ms 314732 KB Output is correct
8 Correct 690 ms 314604 KB Output is correct
9 Correct 879 ms 314364 KB Output is correct
10 Correct 848 ms 314348 KB Output is correct
11 Correct 368 ms 313580 KB Output is correct
12 Correct 371 ms 313580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 170 ms 313452 KB Output is correct
2 Correct 175 ms 313580 KB Output is correct
3 Correct 170 ms 313580 KB Output is correct
4 Correct 167 ms 313452 KB Output is correct
5 Correct 170 ms 313452 KB Output is correct
6 Correct 172 ms 313484 KB Output is correct
7 Correct 169 ms 313452 KB Output is correct
8 Correct 189 ms 313580 KB Output is correct
9 Correct 194 ms 313796 KB Output is correct
10 Correct 190 ms 313452 KB Output is correct
11 Correct 666 ms 314724 KB Output is correct
12 Correct 647 ms 314732 KB Output is correct
13 Correct 690 ms 314604 KB Output is correct
14 Correct 879 ms 314364 KB Output is correct
15 Correct 848 ms 314348 KB Output is correct
16 Correct 368 ms 313580 KB Output is correct
17 Correct 371 ms 313580 KB Output is correct
18 Correct 1208 ms 314856 KB Output is correct
19 Correct 1235 ms 314732 KB Output is correct
20 Correct 1572 ms 322284 KB Output is correct
21 Correct 964 ms 319340 KB Output is correct
22 Correct 467 ms 319468 KB Output is correct
23 Correct 480 ms 319932 KB Output is correct
24 Correct 1172 ms 320076 KB Output is correct