#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) + 10;
struct node{
node* c[2];
ll lazy;
ll mx;
node(){c[0] = c[1] = nullptr;lazy = mx = 0;}
void push(ll l , ll r){
if(!lazy) return ;
if(l!=r){
if(!c[0]) c[0] = new node();
if(!c[1]) c[1] = new node();
c[0]->lazy += lazy , c[1]->lazy += lazy;
}
mx+=lazy;
lazy=0;
return ;
}
void pull(ll l, ll r){
push(l,r); ll mid = (l+r)/2;
if(c[0]) c[0]->push(l, mid);
if(c[1]) c[1]->push(mid+1, r);
mx = max(c[0] ? c[0]->mx : 0,c[1] ? c[1]->mx : 0);
}
void upd(ll x , ll y , ll v , ll l = 1 , ll r = MAX){
push(l,r);
ll mid = (l + r)/2;
if(x==l && y==r){
lazy += v;
push(l,r);
return ;
}
if(y <= mid){
if(!c[0]) c[0] = new node();
c[0]->upd(x,y,v,l,mid);
}
else if(x > mid){
if(!c[1]) c[1] = new node();
c[1]->upd(x,y,v,mid+1,r);
}
else{
if(!c[0]) c[0] = new node();
if(!c[1]) c[1] = new node();
c[0]->upd(x,mid,v,l,mid) , c[1]->upd(mid+1,y,v,mid+1,r);
}
pull(l,r);
}
ll qry(ll x , ll y , ll l = 1, ll r = MAX){
push(l,r);
ll mid = l + (r-l)/2;
if(x == l && y == r){
return mx;
}
if(y <= mid){
if(!c[0]) return 0;
return c[0]->qry(x,y,l,mid);
}
else if(x > mid){
if(!c[1]) return 0;
return c[1]->qry(x,y,mid+1,r);
}
else{
return max( (c[0] != nullptr ? c[0]->qry(x,mid,l,mid) : 0) , (c[1] != nullptr ? c[1]->qry(mid+1,y,mid+1,r) : 0));
}
}
};
node* tree;
ll N;
ll cnt1 = 0;
multiset<ll> S;
bool ok(){
ll sum=0;
multiset<ll> vis;
for(ll x : S){
if(x > sum + 1)return 0;
if(x!=1 and vis.find(x)==vis.end()){
vis.insert(x);
ll s2 = tree->qry(x,x);
assert(s2 == x - sum - 1);
}
sum+=x;
}
return 1;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
tree = new node();
tree->upd(1,MAX,-1);
N = coinsCount;
for(int i=0;i<N;i++){
ll val = coins[i];
if(val == 1){
cnt1++;
}
tree->upd(val+1,MAX,-val);
tree->upd(val,val,+val);
S.insert(val);
}
ll mx = tree->qry(2,MAX);
bool OK = ok();
if((mx <=0 and cnt1>0) || N == 0)assert(OK);
return OK;
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(event == -1){
S.erase(S.find(val));
}else S.insert(val);
if(val == 1){
cnt1+=event;
}
tree->upd(val+1,MAX,-sla);
tree->upd(val,val,+sla);
}
ll mx = tree->qry(2,MAX);
bool OK = ok();
if((mx <=0 and cnt1>0))assert(OK);
return OK;
if(N == 0)return true;
if( mx <=0 and cnt1 > 0)return true;
return false;
}
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 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
