Submission #925155

# Submission time Handle Problem Language Result Execution time Memory
925155 2024-02-10T21:25:21 Z myst6 Happiness (Balkan15_HAPPINESS) C++11
60 / 100
1085 ms 496856 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 = 10000000;
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 79 ms 240764 KB Output is correct
2 Correct 41 ms 240724 KB Output is correct
3 Correct 41 ms 240720 KB Output is correct
4 Correct 41 ms 240720 KB Output is correct
5 Correct 41 ms 240620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 79 ms 240764 KB Output is correct
2 Correct 41 ms 240724 KB Output is correct
3 Correct 41 ms 240720 KB Output is correct
4 Correct 41 ms 240720 KB Output is correct
5 Correct 41 ms 240620 KB Output is correct
6 Correct 49 ms 240708 KB Output is correct
7 Correct 44 ms 240636 KB Output is correct
8 Correct 77 ms 241236 KB Output is correct
9 Correct 78 ms 241028 KB Output is correct
10 Correct 72 ms 241204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 79 ms 240764 KB Output is correct
2 Correct 41 ms 240724 KB Output is correct
3 Correct 41 ms 240720 KB Output is correct
4 Correct 41 ms 240720 KB Output is correct
5 Correct 41 ms 240620 KB Output is correct
6 Correct 653 ms 247416 KB Output is correct
7 Correct 631 ms 247332 KB Output is correct
8 Correct 623 ms 247496 KB Output is correct
9 Correct 1085 ms 250208 KB Output is correct
10 Correct 1004 ms 251296 KB Output is correct
11 Correct 497 ms 251908 KB Output is correct
12 Correct 489 ms 251944 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 79 ms 240764 KB Output is correct
2 Correct 41 ms 240724 KB Output is correct
3 Correct 41 ms 240720 KB Output is correct
4 Correct 41 ms 240720 KB Output is correct
5 Correct 41 ms 240620 KB Output is correct
6 Correct 49 ms 240708 KB Output is correct
7 Correct 44 ms 240636 KB Output is correct
8 Correct 77 ms 241236 KB Output is correct
9 Correct 78 ms 241028 KB Output is correct
10 Correct 72 ms 241204 KB Output is correct
11 Correct 653 ms 247416 KB Output is correct
12 Correct 631 ms 247332 KB Output is correct
13 Correct 623 ms 247496 KB Output is correct
14 Correct 1085 ms 250208 KB Output is correct
15 Correct 1004 ms 251296 KB Output is correct
16 Correct 497 ms 251908 KB Output is correct
17 Correct 489 ms 251944 KB Output is correct
18 Runtime error 839 ms 496856 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -