#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
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)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
