oj.uz

Submission #753746

# Submission time Handle Problem Language Result Execution time Memory
753746 2023-06-05T20:18:50 Z LucaIlie Happiness (Balkan15_HAPPINESS) C++17
10 / 100
 2000 ms 8544 KB 
#include "happiness.h"
#include <bits/stdc++.h>

using namespace std;

int m;
const long long inf = 1e15;
map<long long, int> frecv;
vector<int> v;

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]]++;

    v.clear();
    for ( auto p: frecv ) {
        for ( int j = 0; j < p.second; j++ )
            v.push_back( p.first );
    }
    bool ok = true;
    long long s = 1;
    for ( int i = 0; i < v.size(); i++ ) {
        if ( s < v[i] )
            ok = false;
        s += v[i];
    }

    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]]--;
    }

    v.clear();
    for ( auto p: frecv ) {
        for ( int j = 0; j < p.second; j++ )
            v.push_back( p.first );
    }
    bool ok = true;
    long long s = 1;
    for ( int i = 0; i < v.size(); i++ ) {
        if ( s < v[i] )
            ok = false;
        s += v[i];
    }

    return ok;
}

Compilation message

happiness.cpp: In function 'bool init(int, long long int, long long int*)':
happiness.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for ( int i = 0; i < v.size(); i++ ) {
      |                      ~~^~~~~~~~~~
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:129:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for ( int i = 0; i < v.size(); i++ ) {
      |                      ~~^~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 2 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Execution timed out 2072 ms 8544 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 2 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -