# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
275478 |
2020-08-20T06:14:12 Z |
반딧불(#5115) |
Happiness (Balkan15_HAPPINESS) |
C++17 |
|
1 ms |
384 KB |
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
typedef long long ll;
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;
ll m = (s+e)>>1;
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;
ll m = (s+e)>>1;
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(2*lv < idx) st.insert(idx);
else if(st.find(idx) != st.end()) st.erase(st.find(idx));
if(rv != LLONG_MAX){
if(2*idx < rv) st.insert(rv);
else if(st.find(rv) != st.end()) st.erase(st.find(rv));
}
}
else if(rv != LLONG_MAX){ /// deleted
if(2*lv < rv) st.insert(rv);
else if(st.find(rv) != st.end()) st.erase(st.find(rv));
}
return;
}
ll m = (s+e)>>1;
if(idx <= m){
if(!l) l = new Node(s, m, root);
l->addValue(idx, val);
}
else{
if(!r) r = new Node(m+1, e, root);
r->addValue(idx, val);
}
sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
}
};
Node* root;
int n, cnt;
bool isAble(){
for(auto &x: st){
if(root->minSum(x) + 1 < x) return false;
}
return true;
}
bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
n = coinsCount;
root = new Node();
root->s= 1, root->e = 1e12;
root->root = root;
for(int i=0; i<n; i++){
root->addValue(coins[i], coins[i]);
}
return isAble();
}
bool is_happy(int event, int coinsCount, ll coins[]) {
n += coinsCount * event;
for(int i=0; i<coinsCount; i++) root->addValue(coins[i], event * coins[i]);
return isAble();
}
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 |
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 |
- |