Codeforces Round #305 (Div. 1) B. Mike and Feet

Codeforces Round #305 (Div. 1)に参加しました。ゼロ完。なかったことにしたい。

問題

Problem - 547B - Codeforces

解法

基本的な方針としては以下のような感じ。

各値valに対し「最低でもvalという値を取るような数列の長さのうち最大の長さはいくらか」を覚えておくと,これは単調現象関数になるので,各長さlに対して2分探索して答えを求める。

で,一番難しいのは「最低でもvalという値を取るような数列の長さのうち最大の長さ」を求めるところ。コンテストが終わった後に「各インデックスiに対してiより左側でa[i]より小さい値を取らない最低のインデックスlとiより右側でa[i]より小さい値を取らない最高のインデックスrをセグメント木を使って求める」っていうのを思いついて実装してみたけどTLEした(O(N(log N)^2)になってだいたい10^8くらいの計算量なので1秒だとまぁ厳しいよね)。

じゃあどないすんねんってことだけど,stackを使うとキレイに書ける。

stack s // initially empty
for i = 1 to n
     while s is not empty and a[s.top()] >= a[i]
          do s.pop()
     if s is empty
          then l[i] = 0
     otherwise
          l[i] = s.top()
     s.push(i)

これは思いつかなかった…

以下ソースコード。TLEを修正しながら書いたのでかなりスパゲッティです。

const int MAXN = 1<<18;
const int INF = 1e9+8;

int a[MAXN];
int length[MAXN];
int L[MAXN], R[MAXN];
int K[MAXN];
map<int, int> mm;
stack<int> S;
int N;
int k = 0;

int calc(int l) {
    int low = 1, high = k+1;
    while (high - low > 1) {
        int med = (high+low) / 2;
        if (length[med] >= l) low = med;
        else high = med;
    }
    return K[low];
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", a+i);
        mm[a[i]] = 0;
    }
    {
        for (auto& p : mm) {
            p.second = ++k;
            K[k] = p.first;
        }
    }
    for (int i = 0; i < N; i++) {
        while (!S.empty() && a[S.top()] >= a[i]) {
            S.pop();
        }
        if (S.empty()) L[i] = 0;
        else L[i] = S.top()+1;
        S.push(i);
    }
    while (!S.empty()) S.pop();
    for (int i = N-1; i >= 0; i--) {
        while (!S.empty() && a[S.top()] >= a[i]) {
            S.pop();
        }
        if (S.empty()) R[i] = N-1;
        else R[i] = S.top()-1;
        S.push(i);
    }
    for (int i = 0; i < N; i++) {
        int tmp = mm[a[i]];
        length[tmp] = max(length[tmp], R[i] - L[i] + 1);
    }
    for (int i = k-1; i >= 1; i--) {
        length[i] = max(length[i], length[i+1]);
    }
    for (int i = 0; i < N; i++) {
        printf("%d ", calc(i+1));
    }
    printf("\n");
    return 0;
}