結果

問題 No.2890 Chiffon
ユーザー nono00
提出日時 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';
}
0