Submission #753491

#	Time	Username	Problem	Language	Result	Execution time	Memory
753491		LucaIlie	Happiness (Balkan15_HAPPINESS)	C++17	0 / 100	1 ms	212 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

int mistakes;
set<int> s;
unordered_map<int, int> frecv;

void add( int x ) {
    //printf( "add %d\n", x );
    if ( s.size() == 0 ) {
        s.insert( x );
        return;
    }

    if ( x <= *s.begin() ) {
        if ( 2 * x < *s.begin() )
            mistakes++;
        s.insert( x );
        return;
    }

    if ( (*s.rbegin()) <= x ) {
        if ( 2 * (*s.rbegin()) < x )
            mistakes++;
        s.insert( x );
        return;
    }

    auto u = s.upper_bound( x );
    auto l = u;
    l--;

    int a = *l, b = *u;


    //printf( "in add %d %d %d\n", a, x, b );
    if ( 2 * a < b )
        mistakes--;
    if ( 2 * a < x )
        mistakes++;
    if ( 2 * x < b )
        mistakes++;

    s.insert( x );
}

void remove( int x ) {
    //printf( "remove %d\n", x );
    s.erase( x );

    if ( s.size() == 0 ) {
        return;
    }

    if ( x <= *s.begin() ) {
        if ( 2 * x < *s.begin() )
            mistakes--;
        return;
    }

    if ( (*s.rbegin()) <= x ) {
        if ( 2 * (*s.rbegin()) < x )
            mistakes--;
        return;
    }

    auto u = s.upper_bound( x );
    auto l = u;
    l--;


    int a = *l, b = *u;
    //printf( "in remove %d %d %d\n", a, x, b );

    if ( 2 * a < b )
        mistakes++;
    if ( 2 * a < x )
        mistakes--;
    if ( 2 * x < b )
        mistakes--;

}

bool init( int n, long long m, long long c[] ) {
    mistakes = 0;
    for ( int i = 0; i < n; i++ ) {
        if ( frecv[c[i]] == 0 )
            add( c[i] );
        frecv[c[i]]++;
        //printf( "mistakes %d\n", mistakes );
    }
    return (mistakes == 0);
}

bool is_happy( int event, int n, long long c[] ) {
    for ( int i = 0; i < n; i++ ) {
        if ( event == 1 ) {
            if ( frecv[c[i]] == 0 )
                add( c[i] );
            frecv[c[i]]++;
        } else {
            frecv[c[i]]--;
            if ( frecv[c[i]] == 0 )
                remove( c[i] );
        }
        //printf( "mistakes %d\n", mistakes );
    }
    return (mistakes == 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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40