#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int MAXVAL = 8e6;
ll M;
map<ll, int> MM;
struct Node
{
ll val, sum, pos;
int lc, rc;
Node() : val(0), sum(0), lc(-1), rc(-1), pos(-1) {}
};
Node nodes[MAXVAL];
int ncnt=0;
int newNode()
{
return ncnt++;
}
void update(int node, ll tl, ll tr, vector<pll> &V)
{
if(tl==tr)
{
for(auto it : V) nodes[node].sum+=it.second, nodes[node].val+=it.second;
return;
}
ll mid=tl+tr>>1;
if(nodes[node].pos!=-1)
{
if(nodes[node].pos<=mid)
{
if(nodes[node].lc==-1) nodes[node].lc=newNode();
nodes[nodes[node].lc].pos=nodes[node].pos;
nodes[nodes[node].lc].val=nodes[node].val;
}
else
{
if(nodes[node].rc==-1) nodes[node].rc=newNode();
nodes[nodes[node].rc].pos=nodes[node].pos;
nodes[nodes[node].rc].val=nodes[node].val;
}
nodes[node].pos=-1;
}
if(V.size()==1)
{
nodes[node].pos=V[0].first; nodes[node].val=V[0].second;
return;
}
vector<pll> L, R;
for(auto it : V)
{
if(it.first<=mid) L.push_back(it);
else R.push_back(it);
}
if(!L.empty())
{
if(nodes[node].lc==-1) nodes[node].lc=newNode();
update(nodes[node].lc, tl, mid, L);
}
if(!R.empty())
{
if(nodes[node].rc==-1) nodes[node].rc=newNode();
update(nodes[node].rc, mid+1, tr, R);
}
nodes[node].sum=0; nodes[node].val=0;
if(nodes[node].lc!=-1) nodes[node].sum+=nodes[nodes[node].lc].sum;
if(nodes[node].lc!=-1) nodes[node].val=min(nodes[node].val, nodes[nodes[node].lc].val);
if(nodes[node].rc!=-1) nodes[node].val=min(nodes[node].val, nodes[node].sum+nodes[nodes[node].rc].val);
nodes[node].val=min(nodes[node].val, nodes[node].sum);
if(nodes[node].rc!=-1) nodes[node].sum+=nodes[nodes[node].rc].sum;
}
int root;
ll query()
{
return nodes[root].val;
}
vector<pll> V;
void update2(ll l, ll r, ll x)
{
if(r<l) return;
if(l<=M) V.push_back({l, x});
if(r+1<=M) V.push_back({r+1, -x});
}
void push(ll x)
{
update2(x+1, M, x);
MM[x]++;
if(MM[x]==1)
{
auto it=MM.find(x);
ll val=-x;
if(next(it)!=MM.end()) val+=next(it)->first;
update2(prev(it)->first+1, x, val);
}
}
void pop(ll x)
{
update2(x+1, M, -x);
MM[x]--;
if(MM[x]==0)
{
auto it=MM.find(x);
ll val=x;
if(next(it)!=MM.end()) val-=next(it)->first;
update2(prev(it)->first+1, x, val);
MM.erase(x);
}
}
bool init(int coinsCount, ll maxCoinSize, ll coins[])
{
V.clear();
M=maxCoinSize;
root=newNode();
MM[0];
for(int i=0; i<coinsCount; i++) push(coins[i]);
update(root, 1, M, V);
return query()>=-1;
}
bool is_happy(int event, int coinsCount, ll coins[])
{
V.clear();
if(event==-1) for(int i=0; i<coinsCount; i++) pop(coins[i]);
else for(int i=0; i<coinsCount; i++) push(coins[i]);
update(root, 1, M, V);
return query()>=-1;
}
Compilation message
happiness.cpp: In constructor 'Node::Node()':
happiness.cpp:18:10: warning: 'Node::rc' will be initialized after [-Wreorder]
18 | int lc, rc;
| ^~
happiness.cpp:17:15: warning: 'll Node::pos' [-Wreorder]
17 | ll val, sum, pos;
| ^~~
happiness.cpp:19:2: warning: when initialized here [-Wreorder]
19 | Node() : val(0), sum(0), lc(-1), rc(-1), pos(-1) {}
| ^~~~
happiness.cpp: In function 'void update(int, ll, ll, std::vector<std::pair<long long int, long long int> >&)':
happiness.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | ll mid=tl+tr>>1;
| ~~^~~
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 |
150 ms |
250744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
250744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
250744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
250744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
