Submission #916505

#	Time	Username	Problem	Language	Result	Execution time	Memory
916505		Darren0724	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	39 ms	40896 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define all(x) x.begin(),x.end()
#define abcorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=200005;
const int K=18;
int n;
vector<int> v(N);
int cmp(int i,int j){
    return (v[i]>v[j]?i:j);
}
struct sparse_table{
    vector<vector<int>> mx;
    void init(){
        mx.resize(K,vector<int>(N));
        for(int i=0;i<n;i++){
            mx[0][i]=i;
        }
        for(int i=1;i<K;i++){
            for(int j=0;j+(1<<i)<=n;j++){
                mx[i][j]=cmp(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int ask(int l,int r){
        int p=__lg(r-l);
        return cmp(mx[p][l],mx[p][r-(1<<p)]);
    }
}sp;

int dc(int l,int r,int rec){
    if(r<=l){
        return 0;
    }
    int p=sp.ask(l,r);
    if(rec==-1)rec=p;
    return abs(rec-p)+max(dc(l,p,p),dc(p+1,r,p));
}


int32_t main(){
    abcorz;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    sp.init();
    int ans=dc(0,n,-1);
    cout<<ans<<endl;

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26