oj.uz

Submission #275601

# Submission time Handle Problem Language Result Execution time Memory
275601 2020-08-20T06:43:09 Z 임성재(#5103) Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 88412 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 propagate(int node, ll s, ll e) {
	if(tree[node].lz == 0) return;

	tree[node].v += tree[node].lz;

	if(s != e) {
		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;
		}
		
		tree[tree[node].l].lz += tree[node].lz;
		tree[tree[node].r].lz += tree[node].lz;
	}

	tree[node].lz = 0;
}

void update(int node, ll s, ll e, ll l, ll r, ll x) {
	propagate(node, s, e);

	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		tree[node].lz += x;
		propagate(node, s, e);
		
		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].r].v);
}

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 45 ms 70776 KB Output is correct
2 Correct 43 ms 70776 KB Output is correct
3 Correct 43 ms 70784 KB Output is correct
4 Correct 43 ms 70904 KB Output is correct
5 Correct 44 ms 70808 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 43 ms 70776 KB Output is correct
3 Correct 43 ms 70784 KB Output is correct
4 Correct 43 ms 70904 KB Output is correct
5 Correct 44 ms 70808 KB Output is correct
6 Correct 47 ms 70776 KB Output is correct
7 Correct 47 ms 70776 KB Output is correct
8 Correct 102 ms 71544 KB Output is correct
9 Correct 110 ms 71544 KB Output is correct
10 Correct 94 ms 71416 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 43 ms 70776 KB Output is correct
3 Correct 43 ms 70784 KB Output is correct
4 Correct 43 ms 70904 KB Output is correct
5 Correct 44 ms 70808 KB Output is correct
6 Correct 1333 ms 83008 KB Output is correct
7 Correct 1214 ms 82976 KB Output is correct
8 Correct 1413 ms 83220 KB Output is correct
9 Execution timed out 2078 ms 88412 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 70776 KB Output is correct
2 Correct 43 ms 70776 KB Output is correct
3 Correct 43 ms 70784 KB Output is correct
4 Correct 43 ms 70904 KB Output is correct
5 Correct 44 ms 70808 KB Output is correct
6 Correct 47 ms 70776 KB Output is correct
7 Correct 47 ms 70776 KB Output is correct
8 Correct 102 ms 71544 KB Output is correct
9 Correct 110 ms 71544 KB Output is correct
10 Correct 94 ms 71416 KB Output is correct
11 Correct 1333 ms 83008 KB Output is correct
12 Correct 1214 ms 82976 KB Output is correct
13 Correct 1413 ms 83220 KB Output is correct
14 Execution timed out 2078 ms 88412 KB Time limit exceeded
15 Halted 0 ms 0 KB -