oj.uz

답안 #754093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
754093 2023-06-06T16:55:49 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[] ) {
    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;
      |            ^~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -