/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include "happiness.h"
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
bool debug = false, submit = true;
int N;
ll maxc;
/// ------ Segment Treee --------
ll Nseg[2];
int nct = 0;
struct SEGNODE {
ll s;
int lpt, rpt;
};
vector<SEGNODE> seg; /// max 2e5 unique y, which needs 2^19 for Nseg
void newNode() {
SEGNODE ret = {0LL, -1, -1};
seg.pb(ret);
nct++;
}
void initSeg() {
/// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
Nseg[0] = 1;
Nseg[1] = N;
newNode();
}
ll querySeg(ll qle, ll qri, int v = 0, ll l = Nseg[0], ll r = Nseg[1]) {
if(r < qle || l > qri) return 0LL;
if(qle <= l && r <= qri) return seg[v].s;
int mid = (l + r) / 2;
ll ans1 = 0LL, ans2 = 0LL;
if(qle <= mid && seg[v].lpt != -1 ) {
ans1 = querySeg(qle, qri, seg[v].lpt, l, mid);
}
if(qri >= mid + 1 && seg[v].rpt != -1) {
ans2 = querySeg(qle, qri, seg[v].rpt, mid+1, r);
}
return ans1 + ans2;
}
void updateSeg(ll vtx, ll val, int v = 0, ll l = Nseg[0], ll r = Nseg[1]){
//if(debug) cout << " . update " << v << " (" << seg[v].lpt << "," << seg[v].rpt << ") = " << " {" << l << "," << r << "}" << endl;
if(l == r) { // leaf
seg[v].s += val;
return;
}
ll mid = (l + r) / 2LL;
if(vtx <= mid) {
if(seg[v].lpt == -1 ) {
seg[v].lpt = nct;
newNode();
}
updateSeg(vtx, val, seg[v].lpt, l, mid);
} else {
if(seg[v].rpt == -1 ) {
seg[v].rpt = nct;
newNode();
}
updateSeg(vtx, val, seg[v].rpt, mid+1, r);
}
seg[v].s = ((seg[v].lpt == -1) ? 0 : seg[seg[v].lpt].s ) + ( (seg[v].rpt == -1) ? 0 : seg[seg[v].rpt].s );
}
bool checkHappy() {
if(querySeg(1,1) == 0) return false;
ll sm = seg[0].s;
ll cur = 1LL;
while (sm > cur && cur <= maxc) {
ll ans = querySeg(1, cur);
if(ans < cur) return false;
cur = ans + 1LL;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
N = maxCoinSize;
initSeg();
maxc = 0;
for(int i = 0; i< coinsCount; i++) {
updateSeg(coins[i], coins[i]);
maxc += coins[i];
}
//if(debug) cout << (checkHappy()?1:0) << endl;
return checkHappy();
}
bool is_happy(int event, int coinsCount, long long coins[]){
for(int i = 0; i< coinsCount; i++) {
updateSeg(coins[i], coins[i] * (ll)event);
maxc += coins[i] * (ll)event;
}
//if(debug) cout << (checkHappy()?1:0) << endl;
return checkHappy();
}
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 |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
