oj.uz

Submission #441281

# Submission time Handle Problem Language Result Execution time Memory
441281 2021-07-04T20:24:38 Z JovanB Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 45920 KB 
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;

using ll = long long;

const ll MAXV = 1000000000005LL;
const int MAXC = 18000000;

multiset <ll> brojevi;

int idxx;

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

int cnode(ll r){
    ++idxx;
    seg[idxx].mx = r;
    return idxx;
}

void propagate(int node, ll l, ll r){
    seg[node].mx += seg[node].lazy;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    ll mid = (l+r)/2;
    if(!seg[node].L) seg[node].L = cnode(mid);
    if(!seg[node].R) seg[node].R = cnode(r);
    seg[seg[node].L].lazy += seg[node].lazy;
    seg[seg[node].R].lazy += seg[node].lazy;
    seg[node].lazy = 0;
}

void upd(int node, ll l, ll r, ll tl, ll tr, ll val){
    propagate(node, l, r);
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy += val;
        propagate(node, l, r);
        return;
    }
    ll mid = (l+r)/2;
    if(!seg[node].L) seg[node].L = cnode(mid);
    if(!seg[node].R) seg[node].R = cnode(r);
    upd(seg[node].L, l, mid, tl, tr, val);
    upd(seg[node].R, mid+1, r, tl, tr, val);
    seg[node].mx = max(seg[seg[node].L].mx, seg[seg[node].R].mx);
}

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

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    idxx = 1;
    for(int i=0; i<coinsCount; i++){
        upd(1, 1, MAXV, coins[i]+1, MAXV, -coins[i]);
        brojevi.insert(coins[i]);
    }
    if(brojevi.empty()) return 1;
    ll largest = *brojevi.rbegin();
    return query(1, 1, MAXV, 1, largest) <= 1;
}

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]+1, MAXV, -coins[i]);
            brojevi.insert(coins[i]);
        }
        else{
            upd(1, 1, MAXV, coins[i]+1, MAXV, coins[i]);
            brojevi.erase(brojevi.find(coins[i]));
        }
	}
	if(brojevi.empty()) return 1;
    ll largest = *brojevi.rbegin();
    return query(1, 1, MAXV, 1, largest) <= 1;
}

/*
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 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 5 ms 3148 KB Output is correct
7 Correct 5 ms 3404 KB Output is correct
8 Correct 51 ms 25412 KB Output is correct
9 Correct 49 ms 25612 KB Output is correct
10 Correct 45 ms 24756 KB Output is correct

Subtask #3
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 1242 ms 36688 KB Output is correct
7 Correct 1198 ms 36144 KB Output is correct
8 Correct 1177 ms 36596 KB Output is correct
9 Correct 1882 ms 41940 KB Output is correct
10 Execution timed out 2083 ms 45920 KB Time limit exceeded
11 Halted 0 ms 0 KB -

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 5 ms 3148 KB Output is correct
7 Correct 5 ms 3404 KB Output is correct
8 Correct 51 ms 25412 KB Output is correct
9 Correct 49 ms 25612 KB Output is correct
10 Correct 45 ms 24756 KB Output is correct
11 Correct 1242 ms 36688 KB Output is correct
12 Correct 1198 ms 36144 KB Output is correct
13 Correct 1177 ms 36596 KB Output is correct
14 Correct 1882 ms 41940 KB Output is correct
15 Execution timed out 2083 ms 45920 KB Time limit exceeded
16 Halted 0 ms 0 KB -