Submission #417028

#	Time	Username	Problem	Language	Result	Execution time	Memory
417028		MarcoMeijer	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1802 ms	363252 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const ll  INF	= 1ll<<40ll;
const int MX	= 5e5;
const int N	= 1<<24;
const int MOD	= 1e9+7;

int n;
ll seg[N], pl[N], pr[N];
int segcnt=1;
ll tot = 0;

// sparse seg
void createChildren(int p) {
  if(pl[p]) return;
  pl[p] = segcnt++;
  pr[p] = segcnt++;
}
void addSeg(ll i, ll v, int p=0, ll l=0, ll r=INF-1) {
  if(i < l || i > r) return;
  if(l == r) {
    seg[p] += v;
    tot += v;
    return;
  }
  ll m=(l+r)/2;
  createChildren(p);
  addSeg(i,v,pl[p],l,m);
  addSeg(i,v,pr[p],m+1,r);
  seg[p] = seg[pl[p]]+seg[pr[p]];
}
ll getSeg(ll i, ll j, int p=0, ll l=0, ll r=INF-1) {
  if(j < l || i > r) return 0;
  if(i <= l && j >= r) return seg[p];
  ll m=(l+r)/2;
  if(pl[p]==0) return 0;
  ll a=getSeg(i,j,pl[p],l,m);
  ll b=getSeg(i,j,pr[p],m+1,r);
  return a+b;
}

// problem
bool getAns() {
  ll cur = 1;
  while(cur < tot) {
    ll res = getSeg(0,cur);
    if(res < cur)
      return false;
    cur = res+1;
  }
  return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
  RE(i,coinsCount)
    addSeg(coins[i],1ll*coins[i]);
  return getAns();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
  RE(i,coinsCount)
    addSeg(coins[i],event*coins[i]);
  return getAns();
}

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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40