| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 262581 | KoD | Gap (APIO16_gap) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* @title Template
*/
#include "gap.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
template <class T, class U>
bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
class range {
public:
class iterator {
private:
int64_t M_position;
public:
iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { ++M_position; }
bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
reverse_iterator(int64_t position) noexcept: M_position(position) { }
void operator ++ () noexcept { --M_position; }
bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
iterator begin() const noexcept { return M_first; }
iterator end() const noexcept { return M_last; }
reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#include <type_traits>
#include <iterator>
template <class T>
class rev_impl {
public:
using iterator = decltype(std::declval<T>().rbegin());
private:
const iterator M_begin;
const iterator M_end;
public:
rev_impl(T &&cont) noexcept: M_begin(cont.rbegin()), M_end(cont.rend()) { }
iterator begin() const noexcept { return M_begin; }
iterator end() const noexcept { return M_end; }
};
template <class T>
rev_impl<T> rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
using i32 = int;
using i64 = long long int;
using u32 = unsigned int;
using u64 = unsigned long long int;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
#ifdef LOCAL
std::vector<i64> Values;
i64 Queries;
void MinMax(i64 s, i64 t, i64 *mn, i64 *mx) {
++Queries;
assert(s <= t);
*mn = -1;
for (auto x: Values) {
if (x >= s) {
*mn = x;
break;
}
}
*mx = -1;
for (auto x: rev(Values)) {
if (x <= t) {
*mx = x;
break;
}
}
}
#endif
i64 findGap(i32 T, i64 N) {
assert(T == 1);
std::vector<i64> vec(N + 2);
i32 l = 0, r = N + 1;
vec[l] = -1;
vec[r] = 1000000000000000001;
while (r - l > 1) {
i64 mn, mx;
MinMax(vec[l] + 1, vec[r] - 1, &mn, &mx);
vec[l + 1] = mn;
vec[r - 1] = mx;
++l;
--r;
}
i64 res = 0;
for (auto i: range(1, N)) {
chmax(res, vec[i + 1] - vec[i]);
}
return res;
}
#ifdef LOCAL
int main() {
i32 T; i64 N;
std::cin >> T >> N;
Values.resize(N);
for (auto &x: Values) {
std::cin >> x;
}
std::cout << findGap(T, N) << '\n';
std::cout << Queries << '\n';
return 0;
}
#endif