oj.uz

Submission #512820

# Submission time Handle Problem Language Result Execution time Memory
512820 2022-01-16T18:22:37 Z Eyed Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1613 ms 524292 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MOD = 1e9 + 7;

map<ll, int> numHas;
ll m;

struct node {
	int lN;
	int rN;
	ll a; //max over range
	bool mark;
	ll lazy; //need to add each element in v2	
	node(int l = -1, int r = -1, ll b = 0) : lN(l), rN(r), a(b), mark(false), lazy(0) {};
};

vector<node> st;

void makeLeft(int v) {
	if (st[v].lN == -1) st[v].lN = st.size(), st.push_back(node());
}
void makeRight(int v) {
	if (st[v].rN == -1) st[v].rN = st.size(), st.push_back(node());
}
void makeChild(int v) {
	makeLeft(v);
	makeRight(v);
}
void push(int v) {
	if (st[v].mark) {
		st[v].mark = false;
		makeChild(v);
		st[st[v].lN].mark = true;
		st[st[v].rN].mark = true;
		st[st[v].lN].lazy += st[v].lazy;
		st[st[v].rN].lazy += st[v].lazy;
		st[st[v].lN].a += st[v].lazy;
		st[st[v].rN].a += st[v].lazy;
		st[v].lazy = 0;
	}
}
void upd(int v, ll tl, ll tr, ll x, ll l, ll r) {
	//upd adds x from l to r
	if (l > r) return;
	if (l <= tl && r >= tr) {
		st[v].a += x;
		st[v].lazy += x;
		st[v].mark = true;
		return;
	}
	push(v);
	ll mid = (tl + tr) / 2;
	if (max(l,tl) <= min(r,mid)) makeLeft(v), upd(st[v].lN, tl, mid, x, max(l, tl), min(r, mid));
	if (max(l,mid+1) <= min(r,tr)) makeRight(v), upd(st[v].rN, mid + 1, tr, x, max(l, mid + 1), min(r, tr));
	st[v].a = max((st[v].lN != -1 ? st[st[v].lN].a : 0), (st[v].rN != -1 ? st[st[v].rN].a : 0));
}
void update(ll x, int e) {
	if (numHas.find(x) != numHas.end()) numHas[x]+=e;
	else numHas[x] = e;
	upd(0, 0, m, -e * x, x + 1, m);
	if (e == 1 && numHas[x] == 1) {
		upd(0, 0, m, x, x, x);
	}
	if (e == -1 && numHas[x] == 0) {
		upd(0, 0, m, -x, x, x);
	}
}
bool qry() { return st[0].a <= 1; }
void init() { st.push_back(node()); }

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
	init();
	for (ll i = 0; i < coinsCount; ++i) update(coins[i], 1);
	return qry();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	for (ll i = 0; i < coinsCount; ++i) update(coins[i], event);
	return qry();
}


//ll main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//
//	long long arr[5] = { 1,2,4,8,16 };
//	cout << init(5, 100, arr) << endl;
//	ll a1[2] = { 2,8 };
//	cout << is_happy(-1, 2, a1) << endl;
//	ll a2[3] = { 7,9,2 };
//	cout << is_happy(1, 3, a2) << endl;
//
//	return 0;
//}

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 2496 KB Output is correct
7 Correct 6 ms 4540 KB Output is correct
8 Correct 63 ms 33700 KB Output is correct
9 Correct 60 ms 33808 KB Output is correct
10 Correct 60 ms 33720 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 898 ms 78232 KB Output is correct
7 Correct 938 ms 44848 KB Output is correct
8 Correct 929 ms 78176 KB Output is correct
9 Correct 1476 ms 78112 KB Output is correct
10 Correct 1373 ms 78052 KB Output is correct
11 Correct 598 ms 49724 KB Output is correct
12 Correct 605 ms 49784 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 5 ms 2496 KB Output is correct
7 Correct 6 ms 4540 KB Output is correct
8 Correct 63 ms 33700 KB Output is correct
9 Correct 60 ms 33808 KB Output is correct
10 Correct 60 ms 33720 KB Output is correct
11 Correct 898 ms 78232 KB Output is correct
12 Correct 938 ms 44848 KB Output is correct
13 Correct 929 ms 78176 KB Output is correct
14 Correct 1476 ms 78112 KB Output is correct
15 Correct 1373 ms 78052 KB Output is correct
16 Correct 598 ms 49724 KB Output is correct
17 Correct 605 ms 49784 KB Output is correct
18 Runtime error 1613 ms 524292 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -