[AtCoder] ABC 189 C – Mandarin Orange

2021年2月15日

問題

方針

\( x = A_i \) としたとき、\( i – 1\) 番目から先頭に向かって、\( A_i \leq A_j \) を連続的に満たす \( j \) の個数を \( a \) とします。また、\( i + 1 \) 番目から末尾に向かって、\( A_j \leq A_j \) を連続的に満たす \( j \) の個数を \( b \) とします。このとき、みかんを食べる個数は、\( (a + b + 1)x \) となります。

したがって、全ての \(A_i \) について、\( a, b \) を求めれば良いので、平方分割を使って求めます。平方分割を行うに当たり、数列 \( A \) の大きさを \( 10^4 \) と固定し、\( N \) 以降の \( A_i \) の値は \( 0 \) とします。バケットとなる数列を \( B \) とし、サイズは \( 100 \) とします。このとき、\( B_i \) の値は、\( 100i \leq j < 100(i + 1) \) を満たす \( A_j \) の最小値とします。この値を利用することで、\( a, b \) を高速に求められます。

コード

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

int N;
const int M = 10000;
const int m = 100;
int A[M], B[m];

void init() {
    int min_v = 1000000;
    for (int i = 0; i < m; i++) {
        min_v = 1000000;
        for (int j = i * m; j < (i + 1) * m; j++) {
            min_v = min(min_v, A[j]);
        }
        B[i] = min_v;
    }
}

int getLeft(int i) {
    int ret = 0;
    int b = i / m; // iが所属するバケットの要素番号
    // iが所属するバケット内を走査
    for (int j = i - 1; j >= b * m; j--) {
        if (A[j] >= A[i]) ret++;
        else return ret;
    }
    if (b == 0) return ret;
    b--;
    while (b >= 0) {
        if (B[b] >= A[i]) b--;
        else break;
    }
    if (b == -1) return ret + m * (i / m);
    for (int j = (b + 1) * m - 1; j >= b * m; j--) {
        if (A[j] >= A[i]) ret++;
        else break;
    }
    return ret + m * (i / m - b - 1);
}

int getRight(int i) {
    int b = i / m;
    int ret = 0;
    for (int j = i + 1; j < (b + 1) * m; j++) {
        if (A[j] >= A[i]) ret++;
        else return ret;
    }
    if (b == m - 1) return ret;
    b++;
    while (b < m) {
        if (B[b] >= A[i]) b++;
        else break;
    }
    if (b == m) return ret + m * (m - i / m - 1);
    for (int j = b * m; j < (b + 1) * m; j++) {
        if (A[j] >= A[i]) ret++;
        else break;
    }
    return ret + m * (b - i / m - 1);
}

int main() {
    cin >> N;
    int best = 0;
    fill(A, A + M, 0);
    fill(B, B + m, 0);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    init();
    for (int i = 0; i < N; i++) {
        int l = 1 + getLeft(i) + getRight(i);
        best = max(best, A[i] * l);
    }
    cout << best << "\n";
    return 0;
}