oj.uz

Submission #1041305

# Submission time Handle Problem Language Result Execution time Memory
1041305 2024-08-01T20:46:56 Z ssense Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 663 ms 524288 KB 
#include <iostream>
#include "happiness.h"
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>

#define fr first
#define sc second

using namespace std;

#define int long long

struct Tree
{
    int left, right;
    int sum = 0, mare = 0;
    Tree *leftc = nullptr, *rightc = nullptr;
    Tree(int l, int r)
    {
        left = l; right = r;
    }
    void extend()
    {
        if(!leftc && left < right)
        {
            int mid = left+right>>1;
            leftc = new Tree(left, mid);
            rightc = new Tree(mid+1, right);
        }
    }
    void add(int pos, int val)
    {
        if(left > pos || right < pos)
        {
            return;
        }
        if(left == right)
        {
            sum+=val;
            if(sum == 0)
            {
                mare = 0;
            }
            else
            {
                mare = abs(val);
            }
            return;
        }
        extend();
        leftc->add(pos, val);
        rightc->add(pos, val);
        sum = leftc->sum+rightc->sum;
        mare = max(leftc->mare, rightc->mare-leftc->sum);
    }
};

Tree base(1, 1000000000001);

bool init(int32_t coinCount, int maxCoinSize, int coins[])
{
    for(int i = 0; i < coinCount; i++)
    {
        base.add(coins[i], coins[i]);
    }
    if(base.mare > 1)
    {
        return false;
    }
    return true;
}

bool is_happy(int32_t event, int32_t coinCount, int coins[])
{
    for(int i = 0; i < coinCount; i++)
    {
        base.add(coins[i], (long long)event*coins[i]);
    }
    if(base.mare > 1)
    {
        return false;
    }
    return true;
}
/*
int32_t main()
{
    int32_t n;
    int s;
    cin >> n >> s;
    int c[n];
    for(int i = 0; i < n; i++)
    {
        cin >> c[i];
    }
    if(init(n, s, c))
    {
        cout << "HAPPY" << endl;
    }
    else
    {
        cout << "SAD" << endl;
    }
    int q;
    cin >> q;
    while(q--)
    {
        int32_t nn, event;
        cin >> nn >> event;
        int cc[nn];
        for(int i = 0; i < nn; i++)
        {
            cin >> cc[i];
        }
        if(is_happy(event, nn, cc))
        {
            cout << "HAPPY" << endl;
        }
        else
        {
            cout << "SAD" << endl;
        }
    }
}
*/
/*
5 100
4 8 1 2 16
2
2 -1
2 8
3 1
7 9 2
*/
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Compilation message

happiness.cpp: In member function 'void Tree::extend()':
happiness.cpp:42:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |             int mid = left+right>>1;
      |                       ~~~~^~~~~~
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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 4 ms 4696 KB Output is correct
8 Correct 31 ms 35412 KB Output is correct
9 Correct 32 ms 35648 KB Output is correct
10 Correct 25 ms 34528 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 281 ms 70400 KB Output is correct
7 Correct 310 ms 69712 KB Output is correct
8 Correct 310 ms 70384 KB Output is correct
9 Correct 439 ms 87312 KB Output is correct
10 Correct 460 ms 93180 KB Output is correct
11 Correct 156 ms 48076 KB Output is correct
12 Correct 155 ms 48208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 3 ms 4300 KB Output is correct
7 Correct 4 ms 4696 KB Output is correct
8 Correct 31 ms 35412 KB Output is correct
9 Correct 32 ms 35648 KB Output is correct
10 Correct 25 ms 34528 KB Output is correct
11 Correct 281 ms 70400 KB Output is correct
12 Correct 310 ms 69712 KB Output is correct
13 Correct 310 ms 70384 KB Output is correct
14 Correct 439 ms 87312 KB Output is correct
15 Correct 460 ms 93180 KB Output is correct
16 Correct 156 ms 48076 KB Output is correct
17 Correct 155 ms 48208 KB Output is correct
18 Runtime error 663 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -