Submission #512817

#	Time	Username	Problem	Language	Result	Execution time	Memory
512817		Eyed	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	1896 ms	524292 KiB

happiness

#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, ll> numHas;

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 makeChild(ll v) {
	if (st[v].lN == -1) {
		st[v].lN = st.size();
		st.push_back(node(-1, -1, 0));
	}
	if (st[v].rN == -1) {
		st[v].rN = st.size();
		st.push_back(node(-1, -1, 0));
	}
}
void push(ll 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(ll 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);
	makeChild(v);
	ll mid = (tl + tr) / 2;
	upd(st[v].lN, tl, mid, x, max(l, tl), min(r, mid));
	upd(st[v].rN, mid + 1, tr, x, max(l, mid + 1), min(r, tr));
	st[v].a = max(st[st[v].lN].a, st[st[v].rN].a);
}
void update(ll x, ll e) {
	if (numHas.find(x) != numHas.end()) numHas[x]+=e;
	else numHas[x] = e;
	upd(0, 0, 1e12, -e * x, x + 1, 1e12);
	if (e == 1 && numHas[x] == 1) {
		upd(0, 0, 1e12, x, x, x);
	}
	if (e == -1 && numHas[x] == 0) {
		upd(0, 0, 1e12, -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[]) {
	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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40