#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
int m;
const long long inf = 1e15;
map<long long, int> frecv;
struct SegTree {
struct node {
node *left, *right;
long long minn, lazy;
};
node *createNode() {
node *x = new node;
x->left = x->right = NULL;
x->minn = x->lazy = 0;
return x;
}
node *root;
void propag( node *v, long long l, long long r ) {
v->minn += v->lazy;
if ( l != r ) {
v->left->lazy += v->lazy;
v->right->lazy += v->lazy;
}
v->lazy = 0;
}
void init() {
root = createNode();
}
void update( node *v, long long l, long long r, long long lu, long long ru, long long x ) {
if ( l != r ) {
if ( v->left == NULL )
v->left = createNode();
if ( v->right == NULL )
v->right = createNode();
}
propag( v, l, r );
if ( lu > r || ru < l )
return;
if ( lu <= l && r <= ru ) {
v->lazy += x;
propag( v, l, r );
return;
}
long long mid = (l + r) / 2;
update( v->left, l, mid, lu, ru, x );
update( v->right, mid + 1, r, lu, ru, x );
v->minn = min( v->left->minn, v->right->minn );
}
void update( long long l, long long r, long long x ) {
update( root, 0, m, l, r, x );
}
long long queryALL() {
return root->minn;
}
};
SegTree aint;
void add( long long x ) {
aint.update( x, m, 2 * x );
if ( frecv[x] == 0 )
aint.update( x - 1, m, -x );
else
aint.update( x, m, -x );
frecv[x]++;
}
void remove( long long x ) {
frecv[x]--;
aint.update( x, m, -2 * x );
if ( frecv[x] == 0 )
aint.update( x - 1, m, x );
else
aint.update( x, m, x );
}
bool init( int n, long long _m, long long c[] ) {
frecv.clear();
m = _m;
aint.init();
for ( int i = 0; i < n; i++ )
frecv[c[i]]++;
bool ok = (frecv[1] >= 1);
long long s = 1;
for ( auto p: frecv ) {
if ( frecv.upper_bound( p.first ) == frecv.end() )
continue;
auto q = *frecv.upper_bound( p.first );
s += p.first * p.second;
if ( s < q.first )
ok = false;
}
return ok;
}
bool is_happy( int event, int n, long long c[] ) {
for ( int i = 0; i < n; i++ ) {
if ( event == 1 )
frecv[c[i]]++;
else {
frecv[c[i]]--;
if ( frecv[c[i]] == 0 )
frecv.erase( c[i] );
}
}
vector<map<long long, int>::const_iterator> er;
for ( auto p = frecv.begin(); p != frecv.end(); p++ ) {
if ( p->second == 0 )
er.push_back( p );
}
for ( auto p: er )
frecv.erase( p );
bool ok = (frecv[1] >= 1);
long long s = 1;
for ( auto p: frecv ) {
if ( p.second == 0 )
continue;
int x = p.first;
while ( frecv.upper_bound( x ) != frecv.end() && frecv.upper_bound( x )->second == 0 )
x = frecv.upper_bound( x )->first;
if ( frecv.upper_bound( x ) == frecv.end() )
continue;
auto q = *frecv.upper_bound( p.first );
s += p.first * p.second;
if ( s < q.first )
ok = false;
}
return ok;
}
Compilation message
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
16 | long long max_code;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
