#include <bits/stdc++.h>
#include "happiness.h"
#include <stdio.h>
#include <stdlib.h>
#define NMAX 200000
#define QMAX 100000
static int N, Q;
static long long M;
static long long coins[NMAX], A[5];
using namespace std;
struct Node{
int64_t sum, tl, tr, lazy, ans, l, r, cnt;
Node(): lazy(0), sum(0), ans(0), l(-1), r(-1), cnt(0) {}
};
Node segtree[NMAX*4];
int cnt=0;
void push_down(int pos){
long long mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(segtree[pos].l==-1){
segtree[pos].l=++cnt;
segtree[segtree[pos].l].tl=segtree[pos].tl;
segtree[segtree[pos].l].tr=mid;
}
if(segtree[pos].r==-1){
segtree[pos].r=++cnt;
segtree[segtree[pos].r].tl=mid+1;
segtree[segtree[pos].r].tr=segtree[pos].tr;
}
return;
}
void expand(int pos){
if(segtree[pos].lazy>0){
push_down(pos);
segtree[segtree[pos].l].sum+=segtree[pos].lazy;
segtree[segtree[pos].r].sum+=segtree[pos].lazy;
segtree[segtree[pos].l].lazy+=segtree[pos].lazy;
segtree[segtree[pos].r].lazy+=segtree[pos].lazy;
segtree[segtree[pos].l].ans+=segtree[pos].lazy;
segtree[segtree[pos].r].ans+=segtree[pos].lazy;
segtree[pos].lazy=0;
}
}
void update(int pos,int left,int right,int value)
{
expand(pos);
if(left==segtree[pos].tl&&right==segtree[pos].tr){
//cout<<segtree[pos].tl<<" "<<segtree[pos].tr<<" "<<value<<endl;
segtree[pos].lazy+=value;
segtree[pos].sum+=value;
segtree[pos].ans+=value;
expand(pos);
return;
}
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
push_down(pos);
if(left>mid) update(segtree[pos].r,left,right,value);
else if(right<=mid) update(segtree[pos].l,left,right,value);
else{
update(segtree[pos].l,left,mid,value);
update(segtree[pos].r,mid+1,right,value);
}
segtree[pos].ans=min(segtree[segtree[pos].l].ans,segtree[segtree[pos].r].ans);
return;
}
void query(int pos,int index,int event){
//cout <<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
expand(pos);
if(segtree[pos].tl==segtree[pos].tr){
if(event==1){
if(segtree[pos].cnt==0) segtree[pos].ans=segtree[pos].sum-index;
segtree[pos].cnt++;
}else{
segtree[pos].cnt--;
if(segtree[pos].cnt==0) segtree[pos].ans=segtree[pos].sum;
}
//cout <<segtree[pos].tl<<" "<<segtree[pos].sum<<" "<<segtree[pos].ans<<endl;
return;
}
push_down(pos);
int mid=(segtree[pos].tl+segtree[pos].tr)/2;
if(index<=mid) query(segtree[pos].l,index,event);
else query(segtree[pos].r,index,event);
segtree[pos].ans=min(segtree[segtree[pos].l].ans,segtree[segtree[pos].r].ans);
return;
}
long long mx;
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
sort(coins,coins+coinsCount);
segtree[0].tl=0;
segtree[0].tr=maxCoinSize;
mx=maxCoinSize;
update(0,0,mx,1);
for (int i = 0; i < coinsCount; ++i)
{
query(0,coins[i],1);
update(0,coins[i]+1,maxCoinSize,coins[i]);
}//cout <<endl;
return segtree[0].ans>=0;
}
bool is_happy(int event, int coinsCount, long long coins[]){
sort(coins,coins+coinsCount);
for (int i = 0; i < coinsCount; ++i)
{
query(0,coins[i],event);
if(event==-1) update(0,coins[i]+1,mx,-coins[i]);
else update(0,coins[i]+1,mx,coins[i]);
//cout <<segtree[0].ans<<endl;
//cout <<segtree[0].sum<<" ";
}
return segtree[0].ans>=0;
}
Compilation message
happiness.cpp: In constructor 'Node::Node()':
happiness.cpp:14:26: warning: 'Node::lazy' will be initialized after [-Wreorder]
14 | int64_t sum, tl, tr, lazy, ans, l, r, cnt;
| ^~~~
happiness.cpp:14:13: warning: 'int64_t Node::sum' [-Wreorder]
14 | int64_t sum, tl, tr, lazy, ans, l, r, cnt;
| ^~~
happiness.cpp:15:5: warning: when initialized here [-Wreorder]
15 | Node(): lazy(0), sum(0), ans(0), l(-1), r(-1), cnt(0) {}
| ^~~~
happiness.cpp: At global scope:
happiness.cpp:11:31: warning: 'A' defined but not used [-Wunused-variable]
11 | static long long coins[NMAX], A[5];
| ^
happiness.cpp:11:18: warning: 'coins' defined but not used [-Wunused-variable]
11 | static long long coins[NMAX], A[5];
| ^~~~~
happiness.cpp:10:18: warning: 'M' defined but not used [-Wunused-variable]
10 | static long long M;
| ^
happiness.cpp:9:15: warning: 'Q' defined but not used [-Wunused-variable]
9 | static int N, Q;
| ^
happiness.cpp:9:12: warning: 'N' defined but not used [-Wunused-variable]
9 | static int N, Q;
| ^
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 |
10 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
51804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
