# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
275364 | 2020-08-20T05:42:46 Z | 문홍윤(#5111) | Happiness (Balkan15_HAPPINESS) | C++17 | 1387 ms | 125000 KB |
#include "happiness.h" #include <bits/stdc++.h> using namespace std; typedef long long LL; const LL INF=1e12; LL sum; struct NODE{ LL b; int l, r; }tree[20000010]; int re=1; void update(int nd, LL s, LL e, LL num, LL val){ if(s==e){ tree[nd].b+=val; return; } if(num<=(s+e)/2){ if(!tree[nd].l)tree[nd].l=++re; update(tree[nd].l, s, (s+e)/2, num, val); } else{ if(!tree[nd].r)tree[nd].r=++re; update(tree[nd].r, (s+e)/2+1, e, num, val); } tree[nd].b=0; if(tree[nd].l)tree[nd].b+=tree[tree[nd].l].b; if(tree[nd].r)tree[nd].b+=tree[tree[nd].r].b; } inline void update(LL num, LL val){update(1, 1ll, INF, num, val);} LL query(int nd, LL s, LL e, LL a, LL b){ if(e<a||s>b)return 0ll; if(a<=s&&e<=b)return tree[nd].b; LL ret=0; if(tree[nd].l)ret+=query(tree[nd].l, s, (s+e)/2, a, b); if(tree[nd].r)ret+=query(tree[nd].r, (s+e)/2+1, e, a, b); return ret; } inline LL query(LL a, LL b){return query(1, 1ll, INF, a, b);} inline bool poss(){ LL pos=0; while(1){ if(pos==sum)return true; LL tmp=query(1ll, pos+1); if(tmp==pos)return false; pos=tmp; } } bool init(int coinsCount, LL maxCoinSize, LL coins[]) { for(int i=0; i<coinsCount; i++){ update(coins[i], coins[i]); sum+=coins[i]; } return poss(); } bool is_happy(int event, int coinsCount, LL coins[]) { for(int i=0; i<coinsCount; i++){ update(coins[i], coins[i]*(LL)event); sum+=coins[i]*(LL)event; } return poss(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 896 KB | Output is correct |
7 | Correct | 3 ms | 896 KB | Output is correct |
8 | Correct | 24 ms | 4864 KB | Output is correct |
9 | Correct | 24 ms | 4992 KB | Output is correct |
10 | Correct | 21 ms | 4864 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 634 ms | 12344 KB | Output is correct |
7 | Correct | 673 ms | 12260 KB | Output is correct |
8 | Correct | 854 ms | 12420 KB | Output is correct |
9 | Correct | 1049 ms | 15704 KB | Output is correct |
10 | Correct | 838 ms | 16948 KB | Output is correct |
11 | Correct | 269 ms | 11512 KB | Output is correct |
12 | Correct | 289 ms | 11520 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 2 ms | 896 KB | Output is correct |
7 | Correct | 3 ms | 896 KB | Output is correct |
8 | Correct | 24 ms | 4864 KB | Output is correct |
9 | Correct | 24 ms | 4992 KB | Output is correct |
10 | Correct | 21 ms | 4864 KB | Output is correct |
11 | Correct | 634 ms | 12344 KB | Output is correct |
12 | Correct | 673 ms | 12260 KB | Output is correct |
13 | Correct | 854 ms | 12420 KB | Output is correct |
14 | Correct | 1049 ms | 15704 KB | Output is correct |
15 | Correct | 838 ms | 16948 KB | Output is correct |
16 | Correct | 269 ms | 11512 KB | Output is correct |
17 | Correct | 289 ms | 11520 KB | Output is correct |
18 | Correct | 1063 ms | 74308 KB | Output is correct |
19 | Correct | 1165 ms | 77340 KB | Output is correct |
20 | Correct | 1387 ms | 125000 KB | Output is correct |
21 | Correct | 855 ms | 70564 KB | Output is correct |
22 | Correct | 341 ms | 17276 KB | Output is correct |
23 | Correct | 363 ms | 17824 KB | Output is correct |
24 | Correct | 1008 ms | 76656 KB | Output is correct |