Submission #925156

# Submission time Handle Problem Language Result Execution time Memory
925156 2024-02-10T21:26:51 Z myst6 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
1505 ms 524288 KB
#include "happiness.h"
#include <bits/stdc++.h>
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
#pragma GCC target("avx","sse2")

using namespace std;
using ll = long long;

struct Node;

const int sz = 21000000;
int nextfree = 1;
vector<Node> nodes(sz);

struct Node {
	ll tag, mx;
	int left, right;
	Node() : tag(0), mx(0), left(0), right(0) {}
	void extend(ll xl, ll xr) {
		if (xl != xr && !left) {
			left = nextfree++;
			right = nextfree++;
		}
	}
	void apply(ll xl, ll xr) {
		extend(xl, xr);
		if (tag != 0) {
			mx += tag;
			if (left) nodes[left].tag += tag;
			if (right) nodes[right].tag += tag;
			tag = 0;
		}
	}
	void update(ll l, ll r, ll xl, ll xr, ll delta) {
		if (l > r) return;
		if (l == xl && r == xr) {
			tag += delta;
		} else {
			apply(xl, xr);
			ll xm = (xl + xr) / 2;
			nodes[left].update(l, min(r, xm), xl, xm, delta);
			nodes[right].update(max(l, xm+1), r, xm+1, xr, delta);
			nodes[left].apply(xl, xm); nodes[right].apply(xm+1, xr);
			mx = max(nodes[left].mx, nodes[right].mx);
		}
	}
} tree;

ll hi = 1000000000005LL;

unordered_map<ll,int> cnt;

void add(ll coin) {
	cnt[coin] += 1;
	if (cnt[coin] == 1) tree.update(coin, coin, 1, hi, +coin);
	tree.update(coin+1, hi, 1, hi, -coin);
}

void remove(ll coin) {
	cnt[coin] -= 1;
	if (cnt[coin] == 0) tree.update(coin, coin, 1, hi, -coin);
	tree.update(coin+1, hi, 1, hi, +coin);
}

bool check() {
	tree.apply(1, hi);
	return tree.mx <= 1;
}

bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
	hi = maxCoinSize+1;
	cnt.reserve(700000);
	for (int i=0; i<coinsCount; i++) add(coins[i]);
	return check();
}

bool is_happy(int event, int coinsCount, ll coins[]) {
	for (int i=0; i<coinsCount; i++) 
		if (event == 1) add(coins[i]);
		else remove(coins[i]);
	return check();
}

Compilation message

happiness.cpp:3:30: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    3 | #pragma GCC diagnostic error "-std=c++11"
      |                              ^~~~~~~~~~~~
happiness.cpp:4:802: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  ^
happiness.cpp:4:802: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
happiness.cpp:4:802: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
happiness.cpp:4:802: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
    5 | #pragma GCC target("avx","sse2")
      |                                ^
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
happiness.cpp:5:32: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
happiness.cp
# Verdict Execution time Memory Grader output
1 Correct 191 ms 499152 KB Output is correct
2 Correct 90 ms 499028 KB Output is correct
3 Correct 89 ms 499028 KB Output is correct
4 Correct 89 ms 499036 KB Output is correct
5 Correct 92 ms 499024 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 191 ms 499152 KB Output is correct
2 Correct 90 ms 499028 KB Output is correct
3 Correct 89 ms 499028 KB Output is correct
4 Correct 89 ms 499036 KB Output is correct
5 Correct 92 ms 499024 KB Output is correct
6 Correct 92 ms 499024 KB Output is correct
7 Correct 93 ms 499168 KB Output is correct
8 Correct 127 ms 499348 KB Output is correct
9 Correct 130 ms 499540 KB Output is correct
10 Correct 123 ms 499540 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 191 ms 499152 KB Output is correct
2 Correct 90 ms 499028 KB Output is correct
3 Correct 89 ms 499028 KB Output is correct
4 Correct 89 ms 499036 KB Output is correct
5 Correct 92 ms 499024 KB Output is correct
6 Correct 715 ms 505844 KB Output is correct
7 Correct 723 ms 505552 KB Output is correct
8 Correct 674 ms 505684 KB Output is correct
9 Correct 1084 ms 508416 KB Output is correct
10 Correct 1060 ms 509640 KB Output is correct
11 Correct 575 ms 510200 KB Output is correct
12 Correct 565 ms 510292 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 191 ms 499152 KB Output is correct
2 Correct 90 ms 499028 KB Output is correct
3 Correct 89 ms 499028 KB Output is correct
4 Correct 89 ms 499036 KB Output is correct
5 Correct 92 ms 499024 KB Output is correct
6 Correct 92 ms 499024 KB Output is correct
7 Correct 93 ms 499168 KB Output is correct
8 Correct 127 ms 499348 KB Output is correct
9 Correct 130 ms 499540 KB Output is correct
10 Correct 123 ms 499540 KB Output is correct
11 Correct 715 ms 505844 KB Output is correct
12 Correct 723 ms 505552 KB Output is correct
13 Correct 674 ms 505684 KB Output is correct
14 Correct 1084 ms 508416 KB Output is correct
15 Correct 1060 ms 509640 KB Output is correct
16 Correct 575 ms 510200 KB Output is correct
17 Correct 565 ms 510292 KB Output is correct
18 Correct 1389 ms 506588 KB Output is correct
19 Correct 1344 ms 506772 KB Output is correct
20 Runtime error 1505 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -