oj.uz

Submission #275461

# Submission time Handle Problem Language Result Execution time Memory
275461 2020-08-20T06:10:44 Z 임성재(#5103) Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 1063 ms 38264 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;

ll n, m;
int chk[1000010];
ll tree[4000010];
ll lazy[4000010];

void Init(int node, int s, int e) {
	lazy[node] = 0;
	if(s == e) {
		tree[node] = INF - s;
		return;	
	}

	Init(node*2, s, (s+e)/2);
	Init(node*2+1, (s+e)/2+1, e);

	tree[node] = min(tree[node*2], tree[node*2+1]);
}

void propagate(int node, int s, int e) {
	tree[node] += lazy[node];

	if(s != e) {
		lazy[node*2] += lazy[node];
		lazy[node*2+1] += lazy[node];
	}

	lazy[node] = 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) {
		lazy[node] += x;
		propagate(node, s, e);
		
		return;
	}

	update(node*2, s, (s+e)/2, l, r, x);
	update(node*2+1, (s+e)/2+1, e, l, r, x);

	tree[node] = min(tree[node*2], tree[node*2+1]);
}

void chg(int node, int s, int e, int i, ll x) {
	propagate(node, s, e);

	if(s == e) {
		tree[node] += x;
		return;
	}

	int m = (s + e) / 2;
	if(i <= m) chg(node*2, s, m, i, x);
	else chg(node*2+1, m+1, e, i, x);

	propagate(node*2, s, m);
	propagate(node*2+1, m+1, e);

	tree[node] = min(tree[node*2], tree[node*2+1]);
}

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

	Init(1, 0, m);

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

	propagate(1, 0, m);

	return tree[1] >= -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) chg(1, 0, m, coins[i], INF);
		if(chk[coins[i]] == 0 && event == 1) chg(1, 0, m, coins[i], -INF);

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

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

	return tree[1] >= -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 1 ms 288 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 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 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 6 ms 640 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 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 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 733 ms 38156 KB Output is correct
7 Correct 681 ms 38012 KB Output is correct
8 Correct 761 ms 38036 KB Output is correct
9 Correct 1063 ms 38264 KB Output is correct
10 Correct 942 ms 38008 KB Output is correct
11 Correct 471 ms 34808 KB Output is correct
12 Correct 543 ms 34680 KB Output is correct

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 1 ms 288 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 6 ms 640 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -