oj.uz

Submission #276344

# Submission time Handle Problem Language Result Execution time Memory
276344 2020-08-20T12:14:27 Z sjimed Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1620 ms 154120 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

struct Node {
	ll v, lz;
	int l, r;

	Node() {
		v = INF;
		lz = 0;
		l = r = 0;
	}

	Node(ll e) {
		v = INF - e;
		lz = 0;
		l = r = 0;
	}
};

ll sz = 0;
ll n, m;
map<ll,int> chk;
Node tree[3000010];

void update(int node, ll s, ll e, ll l, ll r, ll x) {
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		tree[node].lz += x;
		
		return;
	}

	if(tree[node].l == 0) {
		tree[node].l = sz++;
		tree[tree[node].l].v = INF - (s+e)/2;
	}
	if(tree[node].r == 0) {
		tree[node].r = sz++;
		tree[tree[node].r].v = INF - e;
	}

	update(tree[node].l, s, (s+e)/2, l, r, x);
	update(tree[node].r, (s+e)/2+1, e, l, r, x);

	tree[node].v = min(tree[tree[node].l].v + tree[tree[node].l].lz, tree[tree[node].r].v + tree[tree[node].r].lz);
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	n = coinsCount;
	m = maxCoinSize + 1;

	tree[0].v = INF - m;
	sz++;

	for(int i=0; i<n; i++) {
		if(chk.find(coins[i]) == chk.end()) update(0, 0, m, coins[i], coins[i], -INF);
		
		update(0, 0, m, coins[i]+1, m, coins[i]);
		
		chk[coins[i]]++;
	}

	update(0, 0, m, 0, m, 0);

	return tree[0].v >= -1;
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	n = coinsCount;

	for(int i=0; i<n; i++) {
		if(chk.find(coins[i]) != chk.end() && chk[coins[i]] == 1 && event == -1) update(0, 0, m, coins[i], coins[i], INF);
		if((chk.find(coins[i]) == chk.end() || chk[coins[i]] == 0) && event == 1) update(0, 0, m, coins[i], coins[i], -INF);

		if(event == 1) update(0, 0, m, coins[i]+1, m, coins[i]);
		else update(0, 0, m, coins[i]+1, m, -coins[i]);

		chk[coins[i]] += event;
	}
	
	update(0, 0, m, 0, m, 0);

	return tree[0].v >= -1;
}

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 42 ms 70776 KB Output is correct
2 Correct 50 ms 70776 KB Output is correct
3 Correct 45 ms 70776 KB Output is correct
4 Correct 41 ms 70776 KB Output is correct
5 Correct 42 ms 70776 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 50 ms 70776 KB Output is correct
3 Correct 45 ms 70776 KB Output is correct
4 Correct 41 ms 70776 KB Output is correct
5 Correct 42 ms 70776 KB Output is correct
6 Correct 45 ms 70904 KB Output is correct
7 Correct 45 ms 70904 KB Output is correct
8 Correct 87 ms 71680 KB Output is correct
9 Correct 83 ms 71672 KB Output is correct
10 Correct 75 ms 71672 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 50 ms 70776 KB Output is correct
3 Correct 45 ms 70776 KB Output is correct
4 Correct 41 ms 70776 KB Output is correct
5 Correct 42 ms 70776 KB Output is correct
6 Correct 1105 ms 86124 KB Output is correct
7 Correct 978 ms 85936 KB Output is correct
8 Correct 1010 ms 86176 KB Output is correct
9 Correct 1606 ms 93432 KB Output is correct
10 Correct 1620 ms 95360 KB Output is correct
11 Correct 749 ms 96508 KB Output is correct
12 Correct 775 ms 96760 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB Output is correct
2 Correct 50 ms 70776 KB Output is correct
3 Correct 45 ms 70776 KB Output is correct
4 Correct 41 ms 70776 KB Output is correct
5 Correct 42 ms 70776 KB Output is correct
6 Correct 45 ms 70904 KB Output is correct
7 Correct 45 ms 70904 KB Output is correct
8 Correct 87 ms 71680 KB Output is correct
9 Correct 83 ms 71672 KB Output is correct
10 Correct 75 ms 71672 KB Output is correct
11 Correct 1105 ms 86124 KB Output is correct
12 Correct 978 ms 85936 KB Output is correct
13 Correct 1010 ms 86176 KB Output is correct
14 Correct 1606 ms 93432 KB Output is correct
15 Correct 1620 ms 95360 KB Output is correct
16 Correct 749 ms 96508 KB Output is correct
17 Correct 775 ms 96760 KB Output is correct
18 Runtime error 358 ms 154120 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -