oj.uz

Submission #441295

# Submission time Handle Problem Language Result Execution time Memory
441295 2021-07-04T21:11:00 Z JovanB Happiness (Balkan15_HAPPINESS) C++17
10 / 100
 2000 ms 12276 KB 
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;

using ll = long long;

ll MAXV = 1000000000000LL;
const int MAXC = 10000000;

int idxx;

struct Segment{
    int L, R;
    ll val;
} seg[MAXC];

void upd(int node, ll l, ll r, ll x, ll val){
    if(l == r){
        seg[node].val += val;
        return;
    }
    ll mid = (l+r)/2;
    if(!seg[node].L) seg[node].L = ++idxx;
    if(!seg[node].R) seg[node].R = ++idxx;
    if(x <= mid) upd(seg[node].L, l, mid, x, val);
    else upd(seg[node].R, mid+1, r, x, val);
    seg[node].val = seg[seg[node].L].val + seg[seg[node].R].val;
}

ll query(int node, ll l, ll r, ll tl, ll tr){
    if(tl > r || l > tr || node == 0) return 0;
    if(tl <= l && r <= tr) return seg[node].val;
    ll mid = (l+r)/2;
    return query(seg[node].L, l, mid, tl, tr) + query(seg[node].R, mid+1, r, tl, tr);
}

bool check(){
    int tr = 1;
    ll svi = query(1, 1, MAXV, 1, MAXV);
    svi = min(svi, MAXV);
    while(tr < svi){
        ll kolko = query(1, 1, MAXV, 1, tr);
        if(kolko < tr) return 0;
        tr = kolko + 1;
    }
    return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    idxx = 1;
    MAXV = maxCoinSize;
    for(int i=0; i<coinsCount; i++){
        upd(1, 1, MAXV, coins[i], coins[i]);
    }
    return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0; i<coinsCount; i++){
        if(event == 1){
            upd(1, 1, MAXV, coins[i], coins[i]);
        }
        else{
            upd(1, 1, MAXV, coins[i], -coins[i]);
        }
	}
    return check();
}

/*
5 100
4 8 1 2 16
2
-1 2 2 8
1 3 7 9 2
*/

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 0 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct
6 Execution timed out 2075 ms 1228 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct
6 Execution timed out 2077 ms 12276 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 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 204 KB Output is correct
6 Execution timed out 2075 ms 1228 KB Time limit exceeded
7 Halted 0 ms 0 KB -