tests/AtCoder/colopl2018-final_C_monotone_minima.cpp

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Link: https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c

Depends on

• Monotone 行最小値問題 (Monotone Minima, in O(H + W log H)) (Optimization/monotone_minima.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c"

#include <bits/stdc++.h>
using namespace std;

#include "monotone_minima.hpp"

// COLOCON 2018 Final C - スペースエクスプローラー高橋君
/*
    M[i][j] = (j - i)^2 は Monge
    列 j に一様に A[j] を加えても Monge
*/
int main() {
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    auto func = [&](long long i, long long j) -> long long {
        return A[j] + (j - i) * (j - i);
    };
    auto res = MonotoneMinima<long long>(N, N, func);
    for (int i = 0; i < N; i++) cout << res[i].first << endl;
}

#line 1 "tests/AtCoder/colopl2018-final_C_monotone_minima.cpp"
#define PROBLEM "https://atcoder.jp/contests/colopl2018-final-open/tasks/colopl2018_final_c"

#include <bits/stdc++.h>
using namespace std;

#line 4 "Optimization/monotone_minima.hpp"
using namespace std;

// find min_j f(i, j) for all i, by Monotone Minima, O(H + W log H)
// f(i, j) must be monotone (argmin is not decreasing)
// slide access OK
template<class VAL, class FUNC> void MonotoneMinimaRec
(int HL, int HR, int WL, int WR, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (HR - HL <= 0) return;
    int HM = (HL + HR) / 2;
    res[HM].second = WL;
    for (int i = WL; i < WR; i++) {
        VAL val = f(HM, i);
        if (res[HM].first > val) res[HM] = make_pair(val, i);
    }
    MonotoneMinimaRec(HL, HM, WL, res[HM].second + 1, f, res);
    MonotoneMinimaRec(HM + 1, HR, res[HM].second, WR, f, res);
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f) {
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    MonotoneMinimaRec(0, H, 0, W, f, res);
    return res;
}
#line 7 "tests/AtCoder/colopl2018-final_C_monotone_minima.cpp"

// COLOCON 2018 Final C - スペースエクスプローラー高橋君
/*
    M[i][j] = (j - i)^2 は Monge
    列 j に一様に A[j] を加えても Monge
*/
int main() {
    long long N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    auto func = [&](long long i, long long j) -> long long {
        return A[j] + (j - i) * (j - i);
    };
    auto res = MonotoneMinima<long long>(N, N, func);
    for (int i = 0; i < N; i++) cout << res[i].first << endl;
}

Back to top page