#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
const ll inf = 1e16;
const ll MAX = (1e12) + 1;
struct node{
node *l,*r;
ll mx;
ll lazy;
ll sum;
node(){
l = r = NULL;
sum = lazy = 0;
mx = 0;
}
void push(ll i,ll j){
if(lazy == 0)return;
mx+=lazy;
if(i == j){
lazy = 0;
return;
}
ll mid = (i+j)/2;
if(l == NULL)l = new node();
if(r == NULL)r = new node();
l->lazy +=lazy;
r->lazy +=lazy;
lazy = 0;
}
void update(ll i,ll j,ll a,ll b,ll val){
push(i,j);
if(i > b || j < a)return;
if(a<=i and j<=b){
lazy+=val;
push(i,j);
return;
}
ll mid = (i+j)/2;
if(!(i>b || mid < a)){
if(l == NULL) l = new node();
l->update(i,mid,a,b,val);
}
if(!(mid+1>b || j < a)){
if(r == NULL)r = new node();
r->update(mid+1,j,a,b,val);
}
mx = max(l!=NULL ? l->mx : -inf,r!=NULL ? r->mx : - inf);
}
ll query(ll i,ll j,ll a,ll b){
push(i,j);
if(a<=i and j<=b)return mx;
ll mid = (i+j)/2;
ll op1 = -inf,op2 = inf;
if(!(i>b || mid < a) and l!=NULL){
op1=l->query(i,mid,a,b);
}
if(!(mid+1>b || j<a) and r!=NULL){
op2 = r->query(mid+1,j,a,b);
}
return max(op1,op2);
}
};
node* tree;
static int N;
static int cnt1 = 0;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
tree = new node();
tree->update(1,MAX,1,MAX,-1);
if(MAX <= maxCoinSize)assert(false);
N = coinsCount;
for(int i=0;i<N;i++){
ll val = coins[i];
if(val == 1){
cnt1++;
}
tree->update(1,MAX,val+1,MAX,-val);
tree->update(1,MAX,val,val,+val);
}
ll mx = tree->query(1,MAX,2,MAX);
if(N == 0)return true;
if( mx <=0 and cnt1 > 0 )return true;
return false;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
N+=coinsCount*event;
for(int i=0;i<coinsCount;i++){
ll val = coins[i];
ll sla = val;
if(event == -1)sla = -sla;
if(val == 1){
cnt1+=event;
}
tree->update(1,MAX,val+1,MAX,-sla);
tree->update(1,MAX,val,val,+sla);
}
ll mx = tree->query(1,MAX,2,MAX);
if(N == 0)return true;
if( mx <=0 and cnt1 > 0 )return true;
return false;
}
Compilation message
happiness.cpp: In member function 'void node::push(ll, ll)':
happiness.cpp:41:6: warning: unused variable 'mid' [-Wunused-variable]
41 | ll mid = (i+j)/2;
| ^~~
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 |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
