oj.uz

Submission #753739

# Submission time Handle Problem Language Result Execution time Memory
753739 2023-06-05T20:05:24 Z LucaIlie Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 1 ms 212 KB 
#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[] ) {
    m = _m;
    aint.init();
    for ( int i = 0; i < n; i++ )
        frecv[c[i]]++;

    bool ok = (frecv[1] >= 1);
    long long s = 0;
    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 ( 2 * s - (s + q.first) < -1 )
            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]]--;
    }

    bool ok = (frecv[1] >= 1);
    long long s = 0;
    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 ( 2 * s - (s + q.first) < -1 )
            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;
      |            ^~~~~~~~

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 -