oj.uz

Submission #441277

# Submission time Handle Problem Language Result Execution time Memory
441277 2021-07-04T20:15:55 Z JovanB Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1579 ms 246776 KB 
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;

using ll = long long;

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

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

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    MAXV = maxCoinSize+5;
    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 25576 KB Output is correct
9 Correct 54 ms 25796 KB Output is correct
10 Correct 49 ms 24916 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 886 ms 39728 KB Output is correct
7 Correct 905 ms 39460 KB Output is correct
8 Correct 815 ms 39868 KB Output is correct
9 Correct 1349 ms 46624 KB Output is correct
10 Correct 1579 ms 50972 KB Output is correct
11 Correct 631 ms 30004 KB Output is correct
12 Correct 612 ms 30148 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 5 ms 3148 KB Output is correct
7 Correct 5 ms 3404 KB Output is correct
8 Correct 51 ms 25576 KB Output is correct
9 Correct 54 ms 25796 KB Output is correct
10 Correct 49 ms 24916 KB Output is correct
11 Correct 886 ms 39728 KB Output is correct
12 Correct 905 ms 39460 KB Output is correct
13 Correct 815 ms 39868 KB Output is correct
14 Correct 1349 ms 46624 KB Output is correct
15 Correct 1579 ms 50972 KB Output is correct
16 Correct 631 ms 30004 KB Output is correct
17 Correct 612 ms 30148 KB Output is correct
18 Runtime error 367 ms 246776 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -