結果

問題 No.2890 Chiffon
ユーザー nono00nono00
提出日時 2024-09-13 23:17:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,925 bytes
コンパイル時間 3,131 ms
コンパイル使用メモリ 260,612 KB
実行使用メモリ 89,536 KB
最終ジャッジ日時 2024-09-13 23:17:49
合計ジャッジ時間 7,270 ms
ジャッジサーバーID
(参考情報)
judge6 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 11 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, l, r) for (ll i = (l); i < (r); i++)
#define rrep(i, r, l) for (ll i = (r); i-- > (l);)
#define all(x) begin(x), end(x)
template <class T>
bool chmin(T& lhs, T rhs) {
return lhs > rhs ? (lhs = rhs, true) : false;
}
template <class T>
bool chmax(T& lhs, T rhs) {
return lhs < rhs ? (lhs = rhs, true) : false;
}
struct IOIO {
IOIO() { cin.tie(0)->sync_with_stdio(0); }
} ioio;
template <class S, class T>
ostream& operator<<(ostream& os, const pair<S, T>& p) {
os << '(' << p.first << ", " << p.second << ')';
return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vs) {
os << '{';
rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", ");
os << '}';
return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& vs) {
os << '{';
for (auto it = vs.begin(); it != vs.end(); it++) {
if (it != vs.begin()) { os << ", "; }
os << *it;
}
os << '}';
return os;
}
template <class T, class U>
ostream& operator<<(ostream& os, const map<T, U>& vs) {
os << '{';
for (auto it = vs.begin(); it != vs.end(); it++) {
if (it != vs.begin()) { os << ", "; }
os << *it;
}
os << '}';
return os;
}
#ifdef DEBUG
void dump_func() { cerr << endl; }
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&&... tail) {
cerr << head;
if (sizeof...(Tail) > 0) { cerr << ", "; }
dump_func(std::move(tail)...);
}
#define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__)
#else
#define dump(...) static_cast<int>(0)
#endif
int main() {
int n, k;
cin >> n >> k;
vector<int> a(k);
rep(i, 0, k) cin >> a[i];
rep(i, 0, k) a.push_back(a[i] + 2 * n);
a.push_back(a[0] + 4 * n);
auto sol = [&](int key) {
vector<int> d(2 * k);
rep(i, 0, 2 * k) d[i] = key - (a[i + 1] - a[i]);
vector<int> to(2 * k, -1);
map<ll, int> mn, mx;
mn[0] = 2 * k;
mx[0] = 2 * k;
ll sum = 0;
const int none = 1e9;
rrep(i, 2 * k, 0) {
sum += d[i];
int mni = none;
{
auto it = mn.upper_bound(sum - key);
if (it != mn.begin()) {
it--;
mni = it->second;
}
}
int mxi = none;
{
auto it = mx.lower_bound(sum);
if (it != mx.end()) { mxi = it->second; }
}
if (mxi < mni) { to[i] = mxi; }
{
auto it = mn.lower_bound(sum);
while (it != mn.end()) { it = mn.erase(it); }
}
{
auto it = mx.begin();
while (it != mx.end() && it->first <= sum) it = mx.erase(it);
}
mn[sum] = i;
mx[sum] = i;
}
const int ng = -2;
vector<int> memo(2 * k, -1);
auto find = [&](auto&& self, int i, int d) -> int {
if (d <= i) { return i; }
if (memo[i] == ng) return ng;
if (memo[i] != -1) { return memo[i] = self(self, memo[i], d); }
if (to[i] != -1) {
return memo[i] = self(self, to[i], d);
} else return memo[i] = ng;
};
rep(i, 0, k) {
if (find(find, i, k + i) == k + i) { return true; }
}
return false;
};
int ok = 0;
int ng = 2 * n + 1;
while (ng - ok > 1) {
int key = (ok + ng) / 2;
if (sol(key)) ok = key;
else ng = key;
}
cout << ok << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0