oj.uz

Submission #275530

# Submission time Handle Problem Language Result Execution time Memory
275530 2020-08-20T06:24:17 Z 임성재(#5103) Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 1560 ms 54572 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(int e) {
		v = INF - e;
		lz = 0;
		l = r = 0;
	}
};

ll n, m;
int chk[1000010];
vector<Node> tree;

void propagate(int node, int s, int 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, int s, int e, int l, int 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[coins[i]] == 0) 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[coins[i]] == 1 && event == -1) update(0, 0, m, coins[i], coins[i], INF);
		if(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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 928 ms 54572 KB Output is correct
7 Correct 1010 ms 54532 KB Output is correct
8 Correct 985 ms 54448 KB Output is correct
9 Correct 1522 ms 54484 KB Output is correct
10 Correct 1560 ms 54340 KB Output is correct
11 Correct 840 ms 26568 KB Output is correct
12 Correct 848 ms 26344 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 1 ms 512 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -