#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
long long m, sum;
vector<long long> seg, lzy, eL, dL, e, d;
bool init(int coinsCount, long long maxCoinSize, long long coins[]);
bool is_happy(int event, int coinsCount, long long coins[]);
int create(long long fim, long long l);
void refresh(int pos, long long ini, long long fim);
void update(int pos, long long ini, long long fim, long long p, long long q, long long val);
long long query(int pos, long long ini, long long fim, long long p, long long q);
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
m = maxCoinSize;
create(0, 0);
create(m, 0);
return is_happy(1, coinsCount, coins);;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
for(int i = 0; i < coinsCount; i++){
sum += event * coins[i];
update(1, 1, m, coins[i], m, event * coins[i]);
}
return query(1, 1, m, 1, sum) >= 0;
}
int create(long long fim, long long l){
seg.push_back(-fim);
lzy.push_back(l);
e.push_back(0);
d.push_back(0);
eL.push_back(0);
dL.push_back(0);
return seg.size() - 1;
}
void refresh(int pos, long long ini, long long fim){
if(lzy[pos] == 0) return;
seg[pos] += lzy[pos];
if(ini != fim){
if(e[pos] == 0) eL[pos] += lzy[pos];
else lzy[e[pos]] += lzy[pos];
if(d[pos] == 0) dL[pos] += lzy[pos];
else lzy[d[pos]] += lzy[pos];
}
lzy[pos] = 0;
}
void update(int pos, long long ini, long long fim, long long p, long long q, long long val){
refresh(pos, ini, fim);
if(ini > q || fim < p) return;
if(ini >= p && fim <= q){
lzy[pos] += val;
refresh(pos, ini, fim);
return;
}
long long mid = (ini + fim) >> 1;
if(p <= mid){
if(e[pos] == 0){
int aux = create(mid, eL[pos]);
eL[pos] = 0;
e[pos] = aux;
}
update(e[pos], ini, mid, p, q, val);
}
if(q > mid){
if(d[pos] == 0){
int aux = create(fim, dL[pos]);
dL[pos] = 0;
d[pos] = aux;
}
update(d[pos], mid + 1, fim, p, q, val);
}
seg[pos] = min(seg[e[pos]], seg[d[pos]]);
}
long long query(int pos, long long ini, long long fim, long long p, long long q){
if(pos == 0) return 5e17 + 10;
if(ini > q || fim < p) return 5e17 + 10;
if(ini >= p && fim <= q) return seg[pos] + lzy[pos];
long long mid = (ini + fim) >> 1;
return min(query(e[pos], ini, mid, p, q), query(d[pos], mid + 1, fim, p, q)) + lzy[pos];
}
Compilation message
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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
