Submission #1041308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041308		ssense	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	868 ms	503892 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;
        }
        int mid = left+right>>1;
        if(pos <= mid)
        {
            if(!leftc)
            {
                leftc = new Tree(left, mid);
            }
            leftc->add(pos, val);
        }
        else
        {
            if(!rightc)
            {
                rightc = new Tree(mid+1, right);
            }
            rightc->add(pos, val);    
        }
        sum = 0;
        mare = -LLONG_MAX;
        if(leftc){sum+=leftc->sum; mare = max(mare, leftc->mare);}
        if(rightc){sum+=rightc->sum;if(!leftc){mare = max(mare, rightc->mare);}}
        if(leftc && rightc){mare = max(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;
      |                       ~~~~^~~~~~
happiness.cpp: In member function 'void Tree::add(long long int, long long int)':
happiness.cpp:66:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         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: 40 / 40