Submission #383127

# Submission time Handle Problem Language Result Execution time Memory
383127 2021-03-28T21:29:19 Z JerryLiu06 Happiness (Balkan15_HAPPINESS) C++11
10 / 100
759 ms 314696 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 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, int l, int 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

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, int, int)':
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:36: warning: unused variable 'mid' [-Wunused-variable]
   20 | ll query(int x, int l, int 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;
      |            ^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 179 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 161 ms 313452 KB Output is correct
4 Correct 161 ms 313452 KB Output is correct
5 Correct 164 ms 313580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 179 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 161 ms 313452 KB Output is correct
4 Correct 161 ms 313452 KB Output is correct
5 Correct 164 ms 313580 KB Output is correct
6 Incorrect 162 ms 313452 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 179 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 161 ms 313452 KB Output is correct
4 Correct 161 ms 313452 KB Output is correct
5 Correct 164 ms 313580 KB Output is correct
6 Incorrect 759 ms 314696 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 179 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 161 ms 313452 KB Output is correct
4 Correct 161 ms 313452 KB Output is correct
5 Correct 164 ms 313580 KB Output is correct
6 Incorrect 162 ms 313452 KB Output isn't correct
7 Halted 0 ms 0 KB -