oj.uz

Submission #1074358

# Submission time Handle Problem Language Result Execution time Memory
1074358 2024-08-25T10:03:00 Z TheEpicCowOfLife Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 223 ms 524288 KB 
#include <cstdio>
#include <algorithm>
#include "happiness.h"
#include <cassert>
#include <vector>
using namespace std;
 
// LAZY CREATE LAZY SEGTREE OF PQ's
// wait nvm
 
/*
Let each segtree node store the minimal value of s_(i-1) - a_i for all a_i in range [sl,sr]
adding a value a_i does a suffix increment
subtracting a value a_i does a suffix decrement
*/
// long long mx_size = 1000000000000; 
long long mcs;
const long long inf = (long long) 2e18;
struct node{
    long long v = inf; // minimum considering the offsets of children and itself.
    long long off = 0;
    int l = 0;
    int r = 0;
};
 
#ifndef DEBUG
    const int st_size = 40000005;
#endif
#ifdef DEBUG
    const int st_size = 10000;
#endif
node default_node;
vector<node> st;
int ncnt = 2;
inline void upd_inv(int si){
    st[si].v = min(st[st[si].l].v,st[st[si].r].v);
    st[si].v += st[si].off;
}
 
void update(int si, long long  sl, long long sr, long long x, long long v){
    if (sl == sr){
        if (v == 1 && st[si].l == 0){
            st[si].v = -sl + st[si].off;
        }
        if (v == -1 && st[si].l == 1){
            st[si].v = inf;
        }
        st[si].l += v;
        return;
    }
    long long mid = (sl + sr)/2;
    if (x <= mid){
        if (st[si].l == 0) st[si].l = ncnt++;
        update(st[si].l,sl,mid,x,v);
    }
    else{
        if (st[si].r == 0) st[si].r = ncnt++;
        update(st[si].r,mid+1,sr,x,v);
    }
    upd_inv(si);
}
 
void rupdate(int si, long long sl, long long sr, long long ql, long long v){
    if (sl >= ql){
        st[si].off += v;
        st[si].v += v;
        return;
    }
    assert(sl != sr);
    long long mid = (sl + sr)/2;
    if (st[si].r == 0) st[si].r = ncnt++;
    rupdate(st[si].r,mid+1,sr,ql,v);
    if (ql <= mid){
        if (st[si].l == 0) st[si].l = ncnt++;
        rupdate(st[si].l,sl,mid,ql,v);
    }
    
    upd_inv(si);
}
int onecnt = 0;
 
void work(long long x, long long v){
    if (x == 1){
        onecnt += v;
    }
    else{
        update(1,1,mcs,x,v);
        
    }
    if (x != mcs){
        rupdate(1,1,mcs,x+1ll,x * v);
    }
    assert(ncnt <= st_size);
}
 
int num = 0;
bool getans(){
    return num == 0 ||(onecnt >= 0 && 1 + st[1].v >= 0);
}
 
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    st = vector<node>(st_size,default_node);
    mcs = maxCoinSize;
    int n = coinsCount;
    num += n;
    for (int i = 0; i < n; i++){
        work(coins[i],1);
    }
    // printf("returned %lld\n", st[1].v);
    return getans();
}
bool is_happy(int event, int coinsCount, long long coins[]){
    for (int i = 0; i < coinsCount; i++){
        work(coins[i],event);
    }
    num += coinsCount * event;
    // printf("returned %lld\n", st[1].v);
 
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -