Submission #383129

# Submission time Handle Problem Language Result Execution time Memory
383129 2021-03-28T21:35:29 Z JerryLiu06 Happiness (Balkan15_HAPPINESS) C++11
60 / 100
1740 ms 524288 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, 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

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;
      |            ^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 178 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 163 ms 313452 KB Output is correct
4 Correct 165 ms 313388 KB Output is correct
5 Correct 162 ms 313452 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 178 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 163 ms 313452 KB Output is correct
4 Correct 165 ms 313388 KB Output is correct
5 Correct 162 ms 313452 KB Output is correct
6 Correct 164 ms 313452 KB Output is correct
7 Correct 165 ms 313452 KB Output is correct
8 Correct 198 ms 313580 KB Output is correct
9 Correct 204 ms 313708 KB Output is correct
10 Correct 189 ms 313708 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 178 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 163 ms 313452 KB Output is correct
4 Correct 165 ms 313388 KB Output is correct
5 Correct 162 ms 313452 KB Output is correct
6 Correct 747 ms 314476 KB Output is correct
7 Correct 776 ms 314732 KB Output is correct
8 Correct 803 ms 314600 KB Output is correct
9 Correct 1029 ms 314716 KB Output is correct
10 Correct 984 ms 314860 KB Output is correct
11 Correct 431 ms 313836 KB Output is correct
12 Correct 438 ms 313964 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 178 ms 313452 KB Output is correct
2 Correct 169 ms 313452 KB Output is correct
3 Correct 163 ms 313452 KB Output is correct
4 Correct 165 ms 313388 KB Output is correct
5 Correct 162 ms 313452 KB Output is correct
6 Correct 164 ms 313452 KB Output is correct
7 Correct 165 ms 313452 KB Output is correct
8 Correct 198 ms 313580 KB Output is correct
9 Correct 204 ms 313708 KB Output is correct
10 Correct 189 ms 313708 KB Output is correct
11 Correct 747 ms 314476 KB Output is correct
12 Correct 776 ms 314732 KB Output is correct
13 Correct 803 ms 314600 KB Output is correct
14 Correct 1029 ms 314716 KB Output is correct
15 Correct 984 ms 314860 KB Output is correct
16 Correct 431 ms 313836 KB Output is correct
17 Correct 438 ms 313964 KB Output is correct
18 Correct 1604 ms 315372 KB Output is correct
19 Correct 1659 ms 319984 KB Output is correct
20 Runtime error 1740 ms 524288 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -