oj.uz

Submission #1041307

# Submission time Handle Problem Language Result Execution time Memory
1041307 2024-08-01T20:50:29 Z ssense Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 657 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, 1);

bool init(int32_t coinCount, int maxCoinSize, int coins[])
{
    base.right = maxCoinSize;
    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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 26 ms 35128 KB Output is correct
9 Correct 27 ms 35676 KB Output is correct
10 Correct 25 ms 34384 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 247 ms 66892 KB Output is correct
7 Correct 229 ms 66380 KB Output is correct
8 Correct 255 ms 66900 KB Output is correct
9 Correct 385 ms 82520 KB Output is correct
10 Correct 436 ms 88404 KB Output is correct
11 Correct 108 ms 44372 KB Output is correct
12 Correct 111 ms 44404 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 3 ms 4700 KB Output is correct
8 Correct 26 ms 35128 KB Output is correct
9 Correct 27 ms 35676 KB Output is correct
10 Correct 25 ms 34384 KB Output is correct
11 Correct 247 ms 66892 KB Output is correct
12 Correct 229 ms 66380 KB Output is correct
13 Correct 255 ms 66900 KB Output is correct
14 Correct 385 ms 82520 KB Output is correct
15 Correct 436 ms 88404 KB Output is correct
16 Correct 108 ms 44372 KB Output is correct
17 Correct 111 ms 44404 KB Output is correct
18 Runtime error 657 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -