oj.uz

Submission #275574

# Submission time Handle Problem Language Result Execution time Memory
275574 2020-08-20T06:34:17 Z 임성재(#5103) Happiness (Balkan15_HAPPINESS) C++17
30 / 100
 2000 ms 57676 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 n, m;
map<ll,ll> chk;
vector<Node> tree;

void propagate(int node, ll s, ll e) {
	tree[node].v += tree[node].lz;

	if(s != e) {
		if(tree[node].l == 0) tree[node].l = tree.size(), tree.eb((s+e)/2);
		if(tree[node].r == 0) tree[node].r = tree.size(), tree.eb(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;
	}

	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.eb(m);

	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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 3704 KB Output is correct
7 Correct 15 ms 6644 KB Output is correct
8 Correct 111 ms 50480 KB Output is correct
9 Correct 114 ms 50480 KB Output is correct
10 Correct 92 ms 25664 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1651 ms 57396 KB Output is correct
7 Correct 1511 ms 57392 KB Output is correct
8 Correct 1474 ms 57676 KB Output is correct
9 Execution timed out 2101 ms 57308 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 9 ms 3704 KB Output is correct
7 Correct 15 ms 6644 KB Output is correct
8 Correct 111 ms 50480 KB Output is correct
9 Correct 114 ms 50480 KB Output is correct
10 Correct 92 ms 25664 KB Output is correct
11 Correct 1651 ms 57396 KB Output is correct
12 Correct 1511 ms 57392 KB Output is correct
13 Correct 1474 ms 57676 KB Output is correct
14 Execution timed out 2101 ms 57308 KB Time limit exceeded
15 Halted 0 ms 0 KB -