#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 = 22'000'000;
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 = 1'000'000'000'005LL;
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(700'000);
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 |
159 ms |
522460 KB |
Output is correct |
| 2 |
Correct |
96 ms |
522576 KB |
Output is correct |
| 3 |
Correct |
92 ms |
522576 KB |
Output is correct |
| 4 |
Correct |
100 ms |
522580 KB |
Output is correct |
| 5 |
Correct |
95 ms |
522444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
522460 KB |
Output is correct |
| 2 |
Correct |
96 ms |
522576 KB |
Output is correct |
| 3 |
Correct |
92 ms |
522576 KB |
Output is correct |
| 4 |
Correct |
100 ms |
522580 KB |
Output is correct |
| 5 |
Correct |
95 ms |
522444 KB |
Output is correct |
| 6 |
Correct |
98 ms |
522664 KB |
Output is correct |
| 7 |
Correct |
97 ms |
522612 KB |
Output is correct |
| 8 |
Correct |
130 ms |
522832 KB |
Output is correct |
| 9 |
Correct |
133 ms |
523204 KB |
Output is correct |
| 10 |
Correct |
125 ms |
522968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
522460 KB |
Output is correct |
| 2 |
Correct |
96 ms |
522576 KB |
Output is correct |
| 3 |
Correct |
92 ms |
522576 KB |
Output is correct |
| 4 |
Correct |
100 ms |
522580 KB |
Output is correct |
| 5 |
Correct |
95 ms |
522444 KB |
Output is correct |
| 6 |
Runtime error |
144 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
159 ms |
522460 KB |
Output is correct |
| 2 |
Correct |
96 ms |
522576 KB |
Output is correct |
| 3 |
Correct |
92 ms |
522576 KB |
Output is correct |
| 4 |
Correct |
100 ms |
522580 KB |
Output is correct |
| 5 |
Correct |
95 ms |
522444 KB |
Output is correct |
| 6 |
Correct |
98 ms |
522664 KB |
Output is correct |
| 7 |
Correct |
97 ms |
522612 KB |
Output is correct |
| 8 |
Correct |
130 ms |
522832 KB |
Output is correct |
| 9 |
Correct |
133 ms |
523204 KB |
Output is correct |
| 10 |
Correct |
125 ms |
522968 KB |
Output is correct |
| 11 |
Runtime error |
144 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
