結果

問題 No.2890 Chiffon
ユーザー nono00nono00
提出日時 2024-09-13 23:17:42
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,760 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 2 ms
6,944 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 2 ms
6,944 KB
testcase_18 WA -
testcase_19 AC 2 ms
6,940 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 TLE -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
権限があれば一括ダウンロードができます

ソースコード

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