Submission #1041307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041307		ssense	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	657 ms	524288 KiB

happiness

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40