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