C - Mandarin Orange

問題

個の数列が与えられる. を求めよ.

atcoder.jp

解法

問題文から上記の言い換えは比較的容易.後はこれを埋めて行けば良い.
これが茶diffと聞いてインフレもここまで来たか…と思ったが、実際は通るらしい.

これでは面白く無いので、解法を考えてみよう.

区間の両端を決めるのは難しい.　区間の片方を固定する　あるいは、数列の値が最小値となる区間を導出するといった方法が考えられる.

今回は後者を使う.

さて、ある値が最小値となる区間を求めようと思うと、　となる を探し出せば良い.も同様なので割愛する.
これを求めるには、をソートしておき、先頭から値を順番に舐めて、その添字の情報を保存しておけば良い.なぜなら、が最小値となる区間は、より小さい値を持つ要素の添字から導出できる.探索済みの配列の添字を高速に探索には、std::setなどの二分探索を用いれば良い.
計算量は.

提出

#include <bits/stdc++.h>

using namespace std;

using Int  = long long;

int main()
{
    Int N; cin >> N;
    vector<pair<Int,Int>>v;
    
    set<Int>rIdx,lIdx;
    
    Int ans = 0;
    
    for(Int i = 0; i < N; ++i)
    {
        Int t; cin >> t;
        v.emplace_back(t,i);
    }
    sort(v.begin(),v.end());
    
    for(int i = 0; i < N; ++i)
    {
        const auto [val,idx] = v[i];
        
        auto itr = rIdx.upper_bound(idx);
        auto it2 = lIdx.upper_bound(-idx);
        
        Int r = -1, l = -1;
        
        if(itr == rIdx.end())
            r = N;
        else
            r = *itr;
        
        if( it2 == lIdx.end())
            l = 0;
        else
            l = abs(*it2) + 1;
        
        ans = max(ans, (r - l) * val);
        
        rIdx.emplace(idx);
        lIdx.emplace(-idx);
    }
    
    cout << ans << endl;
}