oj.uz

Submission #417028

# Submission time Handle Problem Language Result Execution time Memory
417028 2021-06-03T10:44:46 Z MarcoMeijer Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1802 ms 363252 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 31 ms 13556 KB Output is correct
9 Correct 31 ms 13712 KB Output is correct
10 Correct 28 ms 13260 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 770 ms 26028 KB Output is correct
7 Correct 783 ms 25764 KB Output is correct
8 Correct 872 ms 26076 KB Output is correct
9 Correct 1103 ms 31956 KB Output is correct
10 Correct 1068 ms 34036 KB Output is correct
11 Correct 427 ms 17220 KB Output is correct
12 Correct 428 ms 17164 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 31 ms 13556 KB Output is correct
9 Correct 31 ms 13712 KB Output is correct
10 Correct 28 ms 13260 KB Output is correct
11 Correct 770 ms 26028 KB Output is correct
12 Correct 783 ms 25764 KB Output is correct
13 Correct 872 ms 26076 KB Output is correct
14 Correct 1103 ms 31956 KB Output is correct
15 Correct 1068 ms 34036 KB Output is correct
16 Correct 427 ms 17220 KB Output is correct
17 Correct 428 ms 17164 KB Output is correct
18 Correct 1248 ms 210868 KB Output is correct
19 Correct 1302 ms 224708 KB Output is correct
20 Correct 1802 ms 363252 KB Output is correct
21 Correct 977 ms 190404 KB Output is correct
22 Correct 475 ms 22724 KB Output is correct
23 Correct 468 ms 23196 KB Output is correct
24 Correct 1255 ms 206960 KB Output is correct