답안 #383128

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
383128 2021-03-28T21:34:22 Z JerryLiu06 Happiness (Balkan15_HAPPINESS) C++11
60 / 100
1611 ms 514384 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[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

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;
      |            ^~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 250860 KB Output is correct
2 Correct 128 ms 250860 KB Output is correct
3 Correct 126 ms 250860 KB Output is correct
4 Correct 130 ms 250880 KB Output is correct
5 Correct 127 ms 250860 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 250860 KB Output is correct
2 Correct 128 ms 250860 KB Output is correct
3 Correct 126 ms 250860 KB Output is correct
4 Correct 130 ms 250880 KB Output is correct
5 Correct 127 ms 250860 KB Output is correct
6 Correct 130 ms 250860 KB Output is correct
7 Correct 151 ms 250860 KB Output is correct
8 Correct 157 ms 251116 KB Output is correct
9 Correct 155 ms 251116 KB Output is correct
10 Correct 155 ms 251116 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 250860 KB Output is correct
2 Correct 128 ms 250860 KB Output is correct
3 Correct 126 ms 250860 KB Output is correct
4 Correct 130 ms 250880 KB Output is correct
5 Correct 127 ms 250860 KB Output is correct
6 Correct 717 ms 251756 KB Output is correct
7 Correct 714 ms 254956 KB Output is correct
8 Correct 754 ms 254956 KB Output is correct
9 Correct 977 ms 256408 KB Output is correct
10 Correct 959 ms 256236 KB Output is correct
11 Correct 399 ms 254784 KB Output is correct
12 Correct 394 ms 254828 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 250860 KB Output is correct
2 Correct 128 ms 250860 KB Output is correct
3 Correct 126 ms 250860 KB Output is correct
4 Correct 130 ms 250880 KB Output is correct
5 Correct 127 ms 250860 KB Output is correct
6 Correct 130 ms 250860 KB Output is correct
7 Correct 151 ms 250860 KB Output is correct
8 Correct 157 ms 251116 KB Output is correct
9 Correct 155 ms 251116 KB Output is correct
10 Correct 155 ms 251116 KB Output is correct
11 Correct 717 ms 251756 KB Output is correct
12 Correct 714 ms 254956 KB Output is correct
13 Correct 754 ms 254956 KB Output is correct
14 Correct 977 ms 256408 KB Output is correct
15 Correct 959 ms 256236 KB Output is correct
16 Correct 399 ms 254784 KB Output is correct
17 Correct 394 ms 254828 KB Output is correct
18 Runtime error 1611 ms 514384 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -