oj.uz

Submission #753491

# Submission time Handle Problem Language Result Execution time Memory
753491 2023-06-05T10:35:19 Z LucaIlie Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 1 ms 212 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -