提出 #73492191

---

ソースコード 拡げる

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(void){
    ll N;
    cin >> N;
    vector<ll> A(N);
    map<ll, vector<ll>> S;
    for(int i = 0; i < N; i++) {
        cin >> A.at(i);
        S[A.at(i)].push_back(i);
    }
    
    vector<ll> ans(N, 0);
    for(auto[x, D] : S) {
        ll idx = D.at(0);
        ll cnt = 1;
        set<ll> update;
        update.insert(idx);
        for(int i = x + 1; true; i++) {
            if(!S.count(i)) {
                break;
            }
            
            if(lower_bound(S.at(i).begin(), S.at(i).end(), idx) == S.at(i).end()) {
                break;
            }
            
            if(ans.at(idx) != 0) {
                cnt += ans.at(idx);
                break;
            }
            
            cnt++;
            idx = *lower_bound(S.at(i).begin(), S.at(i).end(), idx);
            update.insert(idx);
        }
        
        for(auto u : update) {
            ans.at(u) = cnt;
            cnt--;
        }
    }
    
    ll res = 0;
    for(auto a : ans) {
        chmax(res, a);
    }
    cout << res << endl;
    return 0;
}

提出情報

ジャッジ結果