| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 931840 | dead0ne | Happiness (Balkan15_HAPPINESS) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#include "happiness.h"
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007
#define MX 300005
using namespace std;
struct Node{
ll sum=0, l, r;
Node *lc = nullptr, *rc = nullptr;
Node(ll l, ll r) : l(l), r(r) {}
void extend(){
if(!lc && l<r){
ll m = (l+r)>>1;
lc = new Node(l, m);
rc = new Node(m+1, r);
}
}
void add(ll tar, ll val){
extend();
sum += val;
if(lc){
if(tar <= lc->r){
lc->add(tar, val);
}
else{
rc->add(tar,val);
}
}
}
ll query(int ql, int qr){
if(ql<=l && r<=qr){
return sum;
}
if(l>qr || r<ql){
return 0;
}
extend();
return lc->query(ql, qr) + rc->query(ql, qr);
}
};
Node root(0, 0);
bool is_happy(int event, int coinsCount, long long coins[]){
for(int i=0; i<coinsCount; i++){
root.add(coins[i], coins[i] * (long long)event);
}
ll x = 1;
while(x <= root.sum){
ll res = root.query(1, x);
if(res < x) return false;
x = res+1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
root.r = maxCoinSize;
return is_happy(1, coinsCount, coins);
}
void solve(){
int n,m; cin >> n >> m;
ll arr[n];
for(int i=0; i<n; i++) cin >> arr[i];
cout << init(n, m, arr) << endl;
int q; cin >> q;
while(q--){
int e,sz; cin >> e >> sz;
ll wow[sz];
for(int i=0; i<sz; i++) cin >> wow[i];
cout << is_happy(e, sz, wow) << endl;
}
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);
#ifdef Local
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
/*freopen("nondec.in","r",stdin);
freopen("nondec.out","w",stdout);*/
int t=0;
//cin >> t;
while(t--) solve();
}