#include <bits/stdc++.h>
#pragma GCC target("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "happiness.h"
using namespace std;
typedef long long ll;
unordered_set<ll> st;
struct Node{
ll s, e;
ll sum = 0;
Node *l=nullptr, *r=nullptr, *root=nullptr;
Node(){}
Node(ll s, ll e, Node *root): s(s), e(e), root(root){}
~Node(){
if(l) delete l;
if(r) delete r;
}
ll minSum(ll idx){ /// returning sum
if(idx <= s) return 0;
if(e < idx) return sum;
ll ret = 0;
if(l) ret += l->minSum(idx);
if(r) ret += r->minSum(idx);
return ret;
}
ll minMax(ll idx){ /// returning value
if(idx <= s) return 0;
if(s==e) return s;
ll m = (s+e)/2;
if(idx <= m+1){
if(l) return l->minMax(idx);
return 0;
}
if(r){
ll tmp = r->minMax(idx);
if(tmp) return tmp;
}
if(l){
ll tmp = l->minMax(idx);
if(tmp) return tmp;
}
return 0;
}
ll maxMin(ll idx){ /// returning value
if(e <= idx) return LLONG_MAX;
if(s==e) return s;
ll m = (s+e)/2;
if(m <= idx){
if(r) return r->maxMin(idx);
return LLONG_MAX;
}
if(l){
ll tmp = l->maxMin(idx);
if(tmp != LLONG_MAX) return tmp;
}
if(r){
ll tmp = r->maxMin(idx);
if(tmp != LLONG_MAX) return tmp;
}
return LLONG_MAX;
}
void addValue(ll idx, ll val){
if(s==e){
sum += val;
ll lv = root->minMax(idx);
ll rv = root->maxMin(idx);
if(sum){ /// adding
if(lv*2 < idx) st.insert(idx);
else st.erase(idx);
if(rv != LLONG_MAX){
if(idx*2 < rv) st.insert(rv);
}
}
else{ /// deleted
st.erase(idx);
if(rv != LLONG_MAX){
if(lv*2 < rv) st.insert(rv);
}
}
return;
}
ll m = (s+e)/2;
if(idx <= m){
if(!l) l = new Node(s, m, root);
l->addValue(idx, val);
if(!l->sum) delete l, l=nullptr;
}
else{
if(!r) r = new Node(m+1, e, root);
r->addValue(idx, val);
if(!r->sum) delete r, r=nullptr;
}
sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
}
};
Node* root;
bool isAble(){
for(auto it=st.begin(); it!=st.end(); ++it){
if(root->minSum(*it) + 1 < *it) return false;
}
return true;
}
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
root = new Node();
root->s= 1, root->e = maxCoinSize;
root->root = root;
for(int i=0; i<coinsCount; i++){
root->addValue(coins[i], coins[i]);
}
return isAble();
}
bool is_happy(int event, int coinsCount, ll coins[]){
for(int i=0; i<coinsCount; i++) root->addValue(coins[i], coins[i] * event);
return isAble();
}
Compilation message
happiness.cpp:2:24: error: attribute(target("O3")) is unknown
2 | #pragma GCC target("O3")
| ^
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
