#include <iostream>
#include <vector>
#include <algorithm>
#include <optional>
template<typename T, typename FuncFunctor, typename ConcatFunctor>
class SegmentTree {
private:
std::vector<T> array;
size_t sz;
FuncFunctor func;
ConcatFunctor concat;
inline size_t leftChild(size_t i) {
return 2 * i + 1;
}
inline size_t rightChild(size_t i) {
return 2 * i + 2;
}
bool intersect(const size_t &l1, const size_t &r1, const size_t &l2, const size_t &r2) {
return std::max(l1, l2) < std::min(r1, r2);
}
size_t closestPowerOf2(size_t n) {
if (n == 1)
return 1;
else {
return 2 * closestPowerOf2(n / 2);
}
}
T RecursiveFillValue(size_t l, size_t r, size_t i, const T &value) {
if (l + 1 == r) {
array[i] = value;
return func(array[i]);
} else {
T leftValue = RecursiveFillValue(l, 1 + (l + r - 1) / 2, leftChild(i), value);
T rightValue = RecursiveFillValue(1 + (l + r - 1) / 2, r, rightChild(i), value);
array[i] = concat(leftValue, rightValue);
return array[i];
}
}
T RecursiveFillArray(size_t l, size_t r, size_t i, T *arr) {
if (l + 1 == r) {
array[i] = arr[l];
return func(array[i]);
} else {
T leftValue = RecursiveFillArray(l, 1 + (l + r - 1) / 2, leftChild(i), arr);
T rightValue = RecursiveFillArray(1 + (l + r - 1) / 2, r, rightChild(i), arr);
array[i] = concat(leftValue, rightValue);
return array[i];
}
}
T Query(size_t l, size_t r, size_t lcur, size_t rcur, size_t i) {
if (l <= lcur && rcur <= r) {
if (lcur + 1 == rcur) { // if we're in a leaf
return func(array[i]); // Calculate function value
}
return array[i]; // Otherwise return node value
} else {
size_t midpoint = 1 + (lcur + rcur - 1) / 2;
bool left = intersect(l, r, lcur, midpoint);
bool right = intersect(l, r, midpoint, rcur);
if (left && right) {
return concat(Query(l, r, lcur, midpoint, leftChild(i)), Query(l, r, midpoint, rcur, rightChild(i)));
} else if (left) {
return Query(l, r, lcur, midpoint, leftChild(i));
} else {
return Query(l, r, midpoint, rcur, rightChild(i));
}
}
}
T Set(size_t index, const T &newValue, size_t l, size_t r, size_t i) {
if (l + 1 == r) {
array[i] = newValue;
return func(array[i]);
} else {
size_t midpoint = 1 + (l + r - 1) / 2;
if (index < midpoint) {
array[i] = concat(Set(index, newValue, l, midpoint, leftChild(i)),
((midpoint + 1 == r) ? func(array[rightChild(i)]) : array[rightChild(i)]));
} else {
array[i] = concat(((l + 1 == midpoint) ? func(array[leftChild(i)]) : array[leftChild(i)]),
Set(index, newValue, midpoint, r, rightChild(i)));
}
return array[i];
}
}
std::optional<size_t> KthEntryIndex(size_t k, size_t l, size_t r, size_t i) {
if (l + 1 == r) { // If we are in a leaf, return index
if (k == 1 && func(array[i])) // If we are looking for the first element and leaf satisfies the property
return std::make_optional(l); // Return its index
else
return std::nullopt; // No result
} else {
size_t midpoint = 1 + (l + r - 1) / 2; // Middle of an line
if (l + 1 == midpoint) { // If there is a leaf on the left
if (k == 1 && func(array[leftChild(
i)])) { // If we are looking for the first encounter AND there left child satisfies
return KthEntryIndex(k, l, midpoint, leftChild(i)); // Go to this leaf
} else {
return KthEntryIndex(k - (func(array[leftChild(i)]) ? 1 : 0), midpoint, r,
rightChild(i)); // Otherwise to right subtree
}
} else {
if (k <= array[leftChild(i)]) { // Otherwise if there is enough encounters in the left subtree
return KthEntryIndex(k, l, midpoint, leftChild(i)); // Go to left subtree
} else {
return KthEntryIndex(k - array[leftChild(i)], midpoint, r,
rightChild(i)); // Otherwise proceed to the right
}
}
}
}
public:
T Query(size_t l, size_t r) {
return Query(l, r, 0, sz, 0);
}
void Set(size_t index, const T &newValue) {
Set(index, newValue, 0, sz, 0);
}
size_t size() {
return sz;
}
std::optional<size_t> KthEntryIndex(size_t k, size_t l,
size_t r) { // If function is filter and concat is sum, we can find Kth entry of element with property func(x) = 1
size_t offset = (l == 0) ? 0 : Query(0, l);
size_t offset2 = (l == 0) ? 0 : Query(r, sz);
size_t total = Query(0, sz);
if (total - (offset + offset2) >= k) {
auto answer = KthEntryIndex(k + offset, 0, sz, 0);
if (answer && (*answer < r))
return answer;
return std::nullopt;
} else {
return std::nullopt;
}
}
SegmentTree(size_t size, const T &value = T()) : func(), concat() { // Default constructor
sz = closestPowerOf2(size);
if (sz < size) {
sz *= 2;
}
sz *= 2;
sz--;
array = std::vector<T>(sz);
sz = size;
RecursiveFillValue(0, sz, 0, value); // Initialize structure with value
}
SegmentTree(size_t size, T *arr)
: func(), concat() { // Array constructor. Array size must be greater or equal to sz parameter
sz = closestPowerOf2(size);
if (sz < size) {
sz *= 2;
}
sz *= 2;
sz--;
array = std::vector<T>(sz);
sz = size;
RecursiveFillArray(0, sz, 0, arr); // Initialize structure with array values
}
};
using namespace std;
struct weight_functor {
pair<int, int> operator()(const pair<int, int> &a) {
return a;
}
};
struct weigth_concat_functor {
pair<int, int> operator()(const pair<int, int> &a, const pair<int, int> &b) {
return {min(b.first, a.first + b.first), max(b.second, a.second + b.second)};
}
};
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> firstRequests;
vector<int> secondRequests;
vector<int> sideNumber;
SegmentTree<pair<int, int>, weight_functor, weigth_concat_functor> Stones(n);
int order = 0;
int side = 0;
for (int i = 0; i < n; i++) {
cin >> order >> side;
order--;
if(side == 1) {
Stones.Set(order, {1, 1});
} else {
Stones.Set(order, {-1, -1});
}
pair<int, int> state = Stones.Query(0, n);
bool positiveMax = state.second > 0;
bool negativeMin = state.first < 0;
if(positiveMax && negativeMin)
cout << "?\n";
else if(positiveMax)
cout << ">\n";
else
cout << "<\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
