#include "happiness.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
ll mx;
struct Node{
ll sum, tl, tr, l, r;
Node() : sum(0), l(-1), r(-1){}
};
Node tree[40 * 200010];
int cnt = 2;
void update(int node, ll pos, ll add){
if(tree[node].tl == tree[node].tr && tree[node].tl == pos){
tree[node].sum += add;
return;
}
else{
ll mid = (tree[node].tl + tree[node].tr) / 2;
if(pos <= mid)
{
if(tree[node].l == -1){
tree[node].l = cnt++;
tree[tree[node].l].tl = tree[node].tl;
tree[tree[node].l].tr = mid;
}
update(tree[node].l, pos, add);
}
else
{
if(tree[node].r == -1){
tree[node].r = cnt++;
tree[tree[node].r].tl = mid+1;
tree[tree[node].r].tr = tree[node].tr;
}
update(tree[node].r, pos, add);
}
tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
}
}
ll query(int node, ll l, ll r){
if(tree[node].tl > r || tree[node].tr < l) return 0;
if(l == tree[node].tl && tree[node].tr == r) return tree[node].sum;
else{
ll mid=(tree[node].tl + tree[node].tr) /2;
if(tree[node].l == -1){
tree[node].l = cnt++;
tree[tree[node].l].tl = tree[node].tl;
tree[tree[node].l].tr = mid;
}
if(tree[node].r == -1){
tree[node].r = cnt++;
tree[tree[node].r].tl = mid+1;
tree[tree[node].r].tr = tree[node].tr;
}
if(l > mid) return query(tree[node].r, l, r);
else if(r <= mid) return query(tree[node].l, l, r);
else{
return query(tree[node].l, l, mid) + query(tree[node].r, mid+1, r);
}
}
}
bool check(){
ll coin = 1, tot = query(1, 1, mx);
while(coin <= mx){
ll sum = query(1, 1, coin);
if(sum + 1 > mx) return true;
if(tot == sum) return true;
if(query(1, coin+1, sum+1) == 0) return false;
coin = sum + 1;
}
return true;
}
bool init(int n, ll M, ll a[]){
mx = M;
tree[1].sum = 0;
tree[1].tl = 1;
tree[1].tr = 1e9;
for(int i = 0; i < n; i++)
update(1, a[i], a[i]);
return check();
}
bool is_happy(int e, int n, ll a[]){
for(int i = 0; i < n; i++)
update(1, a[i], a[i]*e);
return check();
}
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 |
138 ms |
313424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
313424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
313424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
313424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
