Submission #997940
Source Code Expand
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author RiaD
*/
#include <iostream>
#include <fstream>
#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#include <stdexcept>
#ifndef SPCPPL_ASSERT
#ifdef SPCPPL_DEBUG
#define SPCPPL_ASSERT(condition) \
if(!(condition)) { \
throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \
}
#else
#define SPCPPL_ASSERT(condition)
#endif
#endif
/**
* Support decrementing and multi-passing, but not declared bidirectional(or even forward) because
* it's reference type is not a reference.
*
* It doesn't return reference because
* 1. Anyway it'll not satisfy requirement [forward.iterators]/6
* If a and b are both dereferenceable, then a == b if and only if *a and
* b are bound to the same object.
* 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator
*
* Note, reverse_iterator is not guaranteed to work now too since it works only with bidirectional iterators,
* but it's seems to work at least on my implementation.
*
* It's not really useful anywhere except iterating anyway.
*/
template <typename T>
class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
public:
explicit IntegerIterator(T value): value(value) {
}
IntegerIterator& operator++() {
++value;
return *this;
}
IntegerIterator operator++(int) {
IntegerIterator copy = *this;
++value;
return copy;
}
IntegerIterator& operator--() {
--value;
return *this;
}
IntegerIterator operator--(int) {
IntegerIterator copy = *this;
--value;
return copy;
}
T operator*() const {
return value;
}
bool operator==(IntegerIterator rhs) const {
return value == rhs.value;
}
bool operator!=(IntegerIterator rhs) const {
return !(*this == rhs);
}
private:
T value;
};
template <typename T>
class IntegerRange {
public:
IntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin <= end);
}
IntegerIterator<T> begin() const {
return IntegerIterator<T>(begin_);
}
IntegerIterator<T> end() const {
return IntegerIterator<T>(end_);
}
private:
T begin_;
T end_;
};
template <typename T>
class ReversedIntegerRange {
typedef std::reverse_iterator<IntegerIterator<T>> IteratorType;
public:
ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) {
SPCPPL_ASSERT(begin >= end);
}
IteratorType begin() const {
return IteratorType(IntegerIterator<T>(begin_));
}
IteratorType end() const {
return IteratorType(IntegerIterator<T>(end_));
}
private:
T begin_;
T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
return ReversedIntegerRange<T>(from + 1, to);
}
#include <utility>
template <typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
return true;
}
template <typename T>
constexpr bool hasBegin(...) {
return false;
}
template <typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;
#include <type_traits>
template <bool b, typename T = void>
using enable_if_t = typename std::enable_if<b, T>::type;
template <typename T, typename Merge>
class SegmentTreeBase {
protected:
SegmentTreeBase(std::size_t n, const T& defaultValue = T(), const Merge& merge = Merge()):
n(n),
defaultValue(defaultValue),
shift(calculateShift(n)),
values(shift << 1, defaultValue),
merge(merge) {
}
template <typename R, typename = enable_if_t<IsContainer<R>::value>>
SegmentTreeBase(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()) :
SegmentTreeBase(
static_cast<std::size_t>(std::distance(std::begin(range), std::end(range))),
defaultValue,
merge
) {
std::copy(std::begin(range), std::end(range), values.begin() + shift);
for (std::size_t index: downrange(shift, static_cast<std::size_t>(1))) {
recalculate(index);
}
}
static std::size_t calculateShift(std::size_t n) {
std::size_t result = 1;
while (result < n) {
result <<= 1;
}
return result;
}
void recalculate(std::size_t index) {
values[index] = merge(values[2 * index], values[2 * index + 1]);
}
std::size_t n;
T defaultValue;
std::size_t shift;
std::vector<T> values;
Merge merge;
};
template <typename T, typename Merge>
class BottomUpSegmentTree: protected SegmentTreeBase<T, Merge> {
public:
template <typename R>
BottomUpSegmentTree(const R& range, const T& defaultValue = T(), const Merge& merge = Merge()):
SegmentTreeBase<T, Merge>(range, defaultValue, merge) {
}
const T& getElement(std::size_t index) {
SPCPPL_ASSERT(index < n);
return values[index + shift];
}
T getResult(std::size_t l, std::size_t r) const {
SPCPPL_ASSERT(l <= r && r <= n);
return internalGetResult(l + shift, r + shift);
}
template <typename Updater>
void update(std::size_t index, const Updater& updater) {
SPCPPL_ASSERT(index < n);
index += shift;
updater(values[index]);
for (std::size_t parent = index / 2; parent > 0; parent /= 2) {
this->recalculate(parent);
}
}
void set(std::size_t index, const T& value) {
return update(index, [&value](T& element) {
element = value;
});
}
protected:
typedef SegmentTreeBase<T, Merge> Base;
using Base::n;
using Base::defaultValue;
using Base::shift;
using Base::values;
using Base::merge;
private:
T internalGetResult(std::size_t l, std::size_t r) const {
if (l == r) {
return defaultValue;
}
if (l & 1) {
return merge(values[l], internalGetResult(l + 1, r));
}
if (r & 1) {
return merge(internalGetResult(l, r - 1), values[r - 1]);
}
return internalGetResult(l / 2, r / 2);
}
};
#include <algorithm>
struct Max {
template <typename T>
T operator()(const T& l, const T& r) const {
return std::max(l, r);
}
};
#include <limits>
template <typename T, typename Enable = std::true_type>
struct NegativeInfinity;
template <typename T>
struct NegativeInfinity<T, typename std::is_integral<T>::type> {
T operator()() const {
return std::numeric_limits<T>::min();
}
};
template <typename T>
struct NegativeInfinity<T, typename std::is_floating_point<T>::type> {
T operator()() const {
static_assert(std::numeric_limits<T>::has_infinity, "");
return -std::numeric_limits<T>::infinity();
}
};
template <typename T>
class BottomUpMaxSegmentTree: public BottomUpSegmentTree<T, Max> {
public:
template <typename R>
BottomUpMaxSegmentTree(
const R& range,
const T& infinity = NegativeInfinity<T>()()
): BottomUpSegmentTree<T, Max>(range, infinity) {
}
void updateMaximum(std::size_t index, const T& value) {
return this->update(index, [&value, this](T& element) {
element = this->merge(element, value);
});
}
};
using namespace std;
class TaskB {
public:
void solve(std::istream& in, std::ostream& out) {
int n;
in >> n;
vector<int> v(n);
for (int i: range(n)) {
in >> v[i];
}
int len = 1;
string s;
in >> s;
while(len - 1 < s.size() && s[len - 1] == 'M') {
++len;
}
BottomUpMaxSegmentTree<int> tree(v);
int ans = std::numeric_limits<int>::max();
for (int i = 0; i + len <= n; ++i) {
ans = min(ans, tree.getResult(i, i + len));
}
out << ans << "\n";
}
};
int main() {
std::ios_base::sync_with_stdio(false);
TaskB solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
in.tie(nullptr);
out << std::fixed;
out.precision(20);
solver.solve(in, out);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - Compression |
User |
riadwaw |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
8767 Byte |
Status |
WA |
Exec Time |
19 ms |
Memory |
1996 KB |
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
0 / 800 |
0 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt |
subtask1 |
sample_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All |
sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, 2_1.txt, 2_2.txt, subtask_1.2_1.txt, subtask_1.2_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_15.txt, subtask_3_16.txt, subtask_3_17.txt, subtask_3_18.txt, subtask_3_19.txt, subtask_3_2.txt, subtask_3_20.txt, subtask_3_21.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name |
Status |
Exec Time |
Memory |
2_1.txt |
AC |
2 ms |
256 KB |
2_2.txt |
AC |
2 ms |
256 KB |
sample_1.txt |
WA |
2 ms |
256 KB |
sample_2.txt |
AC |
2 ms |
256 KB |
sample_3.txt |
WA |
2 ms |
256 KB |
sample_4.txt |
WA |
2 ms |
256 KB |
subtask_1.2_1.txt |
AC |
2 ms |
256 KB |
subtask_1.2_2.txt |
AC |
2 ms |
256 KB |
subtask_1_1.txt |
AC |
19 ms |
1868 KB |
subtask_1_10.txt |
AC |
16 ms |
1868 KB |
subtask_1_2.txt |
AC |
14 ms |
1868 KB |
subtask_1_3.txt |
AC |
12 ms |
1868 KB |
subtask_1_4.txt |
AC |
13 ms |
1792 KB |
subtask_1_5.txt |
AC |
4 ms |
512 KB |
subtask_1_6.txt |
AC |
18 ms |
1868 KB |
subtask_1_7.txt |
AC |
2 ms |
256 KB |
subtask_1_8.txt |
AC |
17 ms |
1868 KB |
subtask_1_9.txt |
AC |
17 ms |
1868 KB |
subtask_2_1.txt |
WA |
13 ms |
1868 KB |
subtask_2_10.txt |
WA |
13 ms |
1868 KB |
subtask_2_2.txt |
WA |
13 ms |
1868 KB |
subtask_2_3.txt |
WA |
13 ms |
1868 KB |
subtask_2_4.txt |
WA |
13 ms |
1868 KB |
subtask_2_5.txt |
AC |
2 ms |
256 KB |
subtask_2_6.txt |
AC |
2 ms |
256 KB |
subtask_2_7.txt |
WA |
2 ms |
256 KB |
subtask_2_8.txt |
WA |
12 ms |
1792 KB |
subtask_2_9.txt |
WA |
5 ms |
640 KB |
subtask_3_1.txt |
WA |
12 ms |
1996 KB |
subtask_3_10.txt |
WA |
13 ms |
1868 KB |
subtask_3_11.txt |
WA |
13 ms |
1868 KB |
subtask_3_12.txt |
AC |
13 ms |
1868 KB |
subtask_3_13.txt |
WA |
13 ms |
1868 KB |
subtask_3_14.txt |
WA |
12 ms |
1868 KB |
subtask_3_15.txt |
AC |
12 ms |
1868 KB |
subtask_3_16.txt |
AC |
12 ms |
1868 KB |
subtask_3_17.txt |
WA |
14 ms |
1868 KB |
subtask_3_18.txt |
WA |
13 ms |
1868 KB |
subtask_3_19.txt |
WA |
13 ms |
1868 KB |
subtask_3_2.txt |
WA |
13 ms |
1868 KB |
subtask_3_20.txt |
WA |
14 ms |
1868 KB |
subtask_3_21.txt |
WA |
13 ms |
1868 KB |
subtask_3_3.txt |
WA |
4 ms |
512 KB |
subtask_3_4.txt |
WA |
12 ms |
1792 KB |
subtask_3_5.txt |
WA |
11 ms |
1792 KB |
subtask_3_6.txt |
WA |
13 ms |
1868 KB |
subtask_3_7.txt |
WA |
13 ms |
1868 KB |
subtask_3_8.txt |
WA |
13 ms |
1868 KB |
subtask_3_9.txt |
WA |
12 ms |
1868 KB |