Submission #224533

#	Time	Username	Problem	Language	Result	Execution time	Memory
224533		danila	돌 무게 재기 (IZhO11_stones)	C++14	0 / 100	5 ms	384 KiB

stones

#include <vector>
#include <set>
#include <iostream>
std::pair<int, int> max_elem = {0, -1};
int count = 0;

auto cmp = [](const std::pair<int, int>& a, const std::pair<int, int>& b) { return a.first > b.first; };
//std::vector<int> mas[2]= {std::vector<int>(100000 + 1, 0), std::vector<int>(100000 + 1, 0)};
std::set<std::pair<int, int>, decltype (cmp)> q(cmp);

bool find (std::vector<int>& mas, int num);

template<typename TypeValue>
class Segment_tree {

    int size_i = 0;
    int size;
    std::vector<TypeValue> value;
    std::vector<bool> balance;
    int scale;

    void build (std::vector<TypeValue> &mas, int left, int right, int cur_top, int sdvig = 0);

public:

    explicit Segment_tree (int num_elem, size_t scale):
        size(num_elem),
        value(4 * num_elem, 0),
        balance(4 * num_elem, true),
        scale(scale) {};

//    explicit Segment_tree (int num_elem, int value):
//        size(num_elem),
//        value(4 * num_elem)
//    {std::vector<TypeValue> m(num_elem, value); build (m, 0, num_elem - 1, 1); };

    void update (TypeValue update_value, int pos, int left, int right, int cur_top = 1);
    void update (TypeValue update_value, int pos) {count = 0; update (update_value, pos, 0, size - 1, 1); size_i++;}
    TypeValue sum (int cur_left, int cur_right, int left, int right, int cur_top = 1);
    TypeValue sum (int left, int right) { return sum (0, size - 1, left, right, 1);};
    bool ok (int right)
    {
        count = 0;
        if (balance[1] == true)
        {
            int tmp = sum (0, size - 1, 0, right, 1);

            if (tmp >= 0)
                return true;
        }

        return false;
    }
};

template<typename TypeValue>
void Segment_tree<TypeValue>::build (std::vector<TypeValue> &mas, int left, int right, int cur_top, int sdvig)
{
    if (left == right)
    {
        value[cur_top] = mas[left];
    }
    else
    {
        int tmp = (left + right) / 2;
        build (mas, left, tmp, 2 * cur_top, sdvig);
        build (mas, tmp + 1, right, 2 * cur_top + 1, sdvig);

        value[cur_top] = value[2 * cur_top] + value[2 * cur_top + 1];
    }
}

template<typename TypeValue>
void Segment_tree<TypeValue>::update (TypeValue update_value, int pos, int left, int right, int cur_top)
{
    if (left == right)
    {
        value[cur_top] = update_value;

        if (update_value == -1)
            balance[cur_top] = false;
        else
            balance[cur_top] = true;
    }
    else
    {
        int tmp = (right + left) / 2;
        if (pos <= tmp)
        {
            update (update_value, pos, left, tmp, 2 * cur_top);
        }
        else
        {
            update (update_value, pos, tmp + 1, right, cur_top * 2 + 1);
        }

        value[cur_top] = value[cur_top * 2] + value[cur_top * 2 + 1];

        if (balance[cur_top*2] && balance[cur_top*2 + 1])
        {
            if (value[cur_top*2] == 0)
            {
                auto it = q.upper_bound ({size - 1 - (tmp), 0});
                if (it != q.end ())
                {
                    if (size - 1 - (*it).first <= right && (*it).second == scale || size - 1 - (*it).first > right)
                        balance[cur_top] = true;
                    else
                        balance[cur_top] = false;
                }
                else
                    balance[cur_top] = true;
            }
            else
            {
                balance[cur_top] = true;
            }
        }
        else
        {
            if ((!balance[cur_top*2] && !balance[cur_top*2 + 1]) || (!balance[cur_top*2] && balance[cur_top*2 + 1]))
            {
                balance[cur_top] = false;
            }
            else
            {
                if (value[cur_top*2] > 0 && value[cur_top*2] + value[cur_top*2 + 1] >= 0)
                    balance[cur_top] = true;
                else
                    balance[cur_top] = false;


            }
        }
    }
}


template<typename TypeValue>
TypeValue Segment_tree<TypeValue>::sum (int cur_left, int cur_right, int left, int right, int cur_top)
{
    if (left > right)
        return 0;

    if (left == cur_left && right == cur_right)
    {
        return value[cur_top];
    }

    int tmp = (cur_left + cur_right) / 2;
    return sum (cur_left, tmp, left, std::min(right, tmp), cur_top * 2) + sum (tmp + 1, cur_right, std::max(left, tmp + 1), right, cur_top * 2 + 1);
}


int main ()
{
    int quantity_of_stones = 0;
    std::cin >> quantity_of_stones;

    std::vector<std::set<int, std::greater<int> >> scales(2);
    int scale_size[2] = {0, 0};


     Segment_tree<int> scales_bit[2] = {Segment_tree<int>(quantity_of_stones + 1, 0),
                                        Segment_tree<int>(quantity_of_stones + 1, 1)};


    for (size_t i = 0; i < quantity_of_stones; i++)
    {
        int number_of_stone = 0,
                scale       = 0;
        std::cin >> number_of_stone >> scale;

        int pos = quantity_of_stones - number_of_stone;
        //mas[0][pos] = (scale == 1 ? 1 : -1);
        //mas[1][pos] = (scale == 2 ? 1 : -1);


        if (scale == 1)
        {
            q.insert ({number_of_stone, scale - 1});
            scales_bit[0].update (1, pos);
            scales_bit[1].update (-1, pos);
            max_elem = std::max(max_elem, {number_of_stone, 0});
        }
        else
        {
            q.insert ({number_of_stone, scale - 1});
            scales_bit[0].update (-1, pos);
            scales_bit[1].update (1, pos);

            max_elem = std::max(max_elem, {number_of_stone, 1});
        }

        scales[scale - 1].insert (number_of_stone);
        (scale == 1 ? scale_size[0]++ : scale_size[1]++);

        if (scale_size[0] > scale_size[1])
        {
            if (max_elem.second == 0 && scales_bit[0].ok (quantity_of_stones - 1))
                std::cout << ">" << "\n";
            else
                std::cout << "?" << "\n";
        }
        else
        {
            if (scale_size[1] > scale_size[0])
            {
                if (max_elem.second == 1 && scales_bit[1].ok (quantity_of_stones - 1))
                    std::cout << "<" << "\n";
                else
                    std::cout << "?" << "\n";
            }
            else
            {
                if (*scales[0].begin () > *scales[1].begin ())
                {
                    if (scales_bit[0].ok (quantity_of_stones - 1))
                        std::cout << ">" << "\n";
                    else
                        std::cout << "?" << "\n";
                }
                else
                {
                    if (scales_bit[1].ok (quantity_of_stones - 1))
                        std::cout << "<" << "\n";
                    else
                        std::cout << "?" << "\n";
                }

            }
        }


    }
}

Compilation message (stderr)

stones.cpp: In function 'int main()':
stones.cpp:168:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (size_t i = 0; i < quantity_of_stones; i++)
                        ~~^~~~~~~~~~~~~~~~~~~~
stones.cpp: In instantiation of 'void Segment_tree<TypeValue>::update(TypeValue, int, int, int, int) [with TypeValue = int]':
stones.cpp:38:70:   required from 'void Segment_tree<TypeValue>::update(TypeValue, int) [with TypeValue = int]'
stones.cpp:182:41:   required from here
stones.cpp:106:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
                     if (size - 1 - (*it).first <= right && (*it).second == scale || size - 1 - (*it).first > right)
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100