Submission #329859

#	Time	Username	Problem	Language	Result	Execution time	Memory
329859		gmyu	Happiness (Balkan15_HAPPINESS)	C++14	0 / 100	1 ms	364 KiB

happiness

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#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>

#include "happiness.h"

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;

/// ------ 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 <=N) {
        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();
    for(int i = 0; i< coinsCount; i++) {
        updateSeg(coins[i], 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);
    }
    if(debug) cout << (checkHappy()?1:0) << endl;
    return checkHappy();
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40