oj.uz

Submission #417027

# Submission time Handle Problem Language Result Execution time Memory
417027 2021-06-03T10:43:37 Z MarcoMeijer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1351 ms 406756 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<<23;
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 4 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 32 ms 13528 KB Output is correct
9 Correct 30 ms 13772 KB Output is correct
10 Correct 28 ms 13164 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 766 ms 28948 KB Output is correct
7 Correct 777 ms 28612 KB Output is correct
8 Correct 832 ms 29000 KB Output is correct
9 Correct 1113 ms 36168 KB Output is correct
10 Correct 1055 ms 38440 KB Output is correct
11 Correct 414 ms 20548 KB Output is correct
12 Correct 410 ms 20792 KB Output is correct

Subtask #4
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 4 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 32 ms 13528 KB Output is correct
9 Correct 30 ms 13772 KB Output is correct
10 Correct 28 ms 13164 KB Output is correct
11 Correct 766 ms 28948 KB Output is correct
12 Correct 777 ms 28612 KB Output is correct
13 Correct 832 ms 29000 KB Output is correct
14 Correct 1113 ms 36168 KB Output is correct
15 Correct 1055 ms 38440 KB Output is correct
16 Correct 414 ms 20548 KB Output is correct
17 Correct 410 ms 20792 KB Output is correct
18 Runtime error 1351 ms 406756 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -