oj.uz

Submission #441280

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

using ll = long long;

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

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

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 236 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 236 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 49 ms 25404 KB Output is correct
9 Correct 49 ms 25544 KB Output is correct
10 Correct 44 ms 24716 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 236 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 809 ms 36652 KB Output is correct
7 Correct 805 ms 36288 KB Output is correct
8 Correct 855 ms 36544 KB Output is correct
9 Correct 1280 ms 42040 KB Output is correct
10 Correct 1503 ms 46440 KB Output is correct
11 Correct 618 ms 26444 KB Output is correct
12 Correct 613 ms 26308 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 236 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 49 ms 25404 KB Output is correct
9 Correct 49 ms 25544 KB Output is correct
10 Correct 44 ms 24716 KB Output is correct
11 Correct 809 ms 36652 KB Output is correct
12 Correct 805 ms 36288 KB Output is correct
13 Correct 855 ms 36544 KB Output is correct
14 Correct 1280 ms 42040 KB Output is correct
15 Correct 1503 ms 46440 KB Output is correct
16 Correct 618 ms 26444 KB Output is correct
17 Correct 613 ms 26308 KB Output is correct
18 Correct 1736 ms 398384 KB Output is correct
19 Correct 1745 ms 417324 KB Output is correct
20 Execution timed out 2101 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -