oj.uz

Submission #441296

# Submission time Handle Problem Language Result Execution time Memory
441296 2021-07-04T21:12:02 Z JovanB Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 524288 KB 
#pragma GCC optimize ("Ofast")
#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 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
20.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 Correct 5 ms 3148 KB Output is correct
7 Correct 6 ms 3404 KB Output is correct
8 Correct 54 ms 25356 KB Output is correct
9 Correct 51 ms 25540 KB Output is correct
10 Correct 49 ms 24752 KB Output is correct

Subtask #3
30.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 Correct 812 ms 36644 KB Output is correct
7 Correct 790 ms 36292 KB Output is correct
8 Correct 790 ms 36684 KB Output is correct
9 Correct 1331 ms 42296 KB Output is correct
10 Correct 1509 ms 46596 KB Output is correct
11 Correct 620 ms 26284 KB Output is correct
12 Correct 621 ms 26216 KB Output is correct

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 Correct 5 ms 3148 KB Output is correct
7 Correct 6 ms 3404 KB Output is correct
8 Correct 54 ms 25356 KB Output is correct
9 Correct 51 ms 25540 KB Output is correct
10 Correct 49 ms 24752 KB Output is correct
11 Correct 812 ms 36644 KB Output is correct
12 Correct 790 ms 36292 KB Output is correct
13 Correct 790 ms 36684 KB Output is correct
14 Correct 1331 ms 42296 KB Output is correct
15 Correct 1509 ms 46596 KB Output is correct
16 Correct 620 ms 26284 KB Output is correct
17 Correct 621 ms 26216 KB Output is correct
18 Correct 1901 ms 395808 KB Output is correct
19 Correct 1824 ms 411972 KB Output is correct
20 Execution timed out 2095 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -