結果

問題 No.711 競技レーティング単調増加
ユーザー rapurasu
提出日時 2018-07-13 09:33:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 864 bytes
コンパイル時間 1,522 ms
コンパイル使用メモリ 166,900 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-06 23:29:54
合計ジャッジ時間 4,843 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL A[200001];
LL B[200011];
int N;
int binary_serach(LL x){
    int lb=-1;
    int ub=200010;
    while(ub-lb>1){
        int mid=(ub+lb)/2;
        if(B[mid]>x){
            ub=mid;
        }else{
            lb=mid;
        }
    }
    return ub;
}
int main(){
    cin>>N;
    REP(i,N){
        cin>>A[i];
        A[i]-=i;
    }
    REP(i,200011){
        B[i]=1e12;
    }
    REP(i,N){
        if(A[i]<=0){
            continue;
        }
        int b=binary_serach(A[i]);
        B[b]=A[i];
        /*cout<<"test"<<endl;
        REP(j,10){
            cout<<B[j]<<endl;
        }*/
        //cout<<b<<" "<<A[i]<<endl;
    }
    /*
    cout<<"end"<<endl;
    REP(i,20){
        cout<<B[i]<<endl;
    }*/
    int ans=0;
    REP(i,200011){
        if(B[i]!=1e12)ans++;
    }
    cout<<N-ans<<endl;
    return(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0