oj.uz

Submission #441279

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

using ll = long long;

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

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 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 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 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 332 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 5 ms 3372 KB Output is correct
8 Correct 49 ms 25348 KB Output is correct
9 Correct 50 ms 25540 KB Output is correct
10 Correct 46 ms 24820 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 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 332 KB Output is correct
6 Correct 800 ms 36648 KB Output is correct
7 Correct 781 ms 36328 KB Output is correct
8 Correct 781 ms 36744 KB Output is correct
9 Correct 1306 ms 42228 KB Output is correct
10 Correct 1486 ms 46544 KB Output is correct
11 Correct 629 ms 26332 KB Output is correct
12 Correct 608 ms 26276 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 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 332 KB Output is correct
6 Correct 5 ms 3148 KB Output is correct
7 Correct 5 ms 3372 KB Output is correct
8 Correct 49 ms 25348 KB Output is correct
9 Correct 50 ms 25540 KB Output is correct
10 Correct 46 ms 24820 KB Output is correct
11 Correct 800 ms 36648 KB Output is correct
12 Correct 781 ms 36328 KB Output is correct
13 Correct 781 ms 36744 KB Output is correct
14 Correct 1306 ms 42228 KB Output is correct
15 Correct 1486 ms 46544 KB Output is correct
16 Correct 629 ms 26332 KB Output is correct
17 Correct 608 ms 26276 KB Output is correct
18 Runtime error 1256 ms 489636 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -