oj.uz

Submission #1041308

# Submission time Handle Problem Language Result Execution time Memory
1041308 2024-08-01T20:58:28 Z ssense Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 868 ms 503892 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;
        }
        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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 2416 KB Output is correct
7 Correct 2 ms 2584 KB Output is correct
8 Correct 19 ms 18372 KB Output is correct
9 Correct 23 ms 18524 KB Output is correct
10 Correct 18 ms 18012 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 239 ms 45396 KB Output is correct
7 Correct 205 ms 44752 KB Output is correct
8 Correct 210 ms 45392 KB Output is correct
9 Correct 341 ms 58448 KB Output is correct
10 Correct 359 ms 63952 KB Output is correct
11 Correct 119 ms 44368 KB Output is correct
12 Correct 121 ms 44376 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 2416 KB Output is correct
7 Correct 2 ms 2584 KB Output is correct
8 Correct 19 ms 18372 KB Output is correct
9 Correct 23 ms 18524 KB Output is correct
10 Correct 18 ms 18012 KB Output is correct
11 Correct 239 ms 45396 KB Output is correct
12 Correct 205 ms 44752 KB Output is correct
13 Correct 210 ms 45392 KB Output is correct
14 Correct 341 ms 58448 KB Output is correct
15 Correct 359 ms 63952 KB Output is correct
16 Correct 119 ms 44368 KB Output is correct
17 Correct 121 ms 44376 KB Output is correct
18 Correct 547 ms 299092 KB Output is correct
19 Correct 530 ms 310760 KB Output is correct
20 Correct 868 ms 503892 KB Output is correct
21 Correct 484 ms 263648 KB Output is correct
22 Correct 171 ms 50004 KB Output is correct
23 Correct 200 ms 50516 KB Output is correct
24 Correct 486 ms 286800 KB Output is correct