Submission #968115

#	Time	Username	Problem	Language	Result	Execution time	Memory
968115		Darren0724	Real Mountains (CCO23_day1problem2)	C++17	6 / 25	5048 ms	28704 KiB

Main

#pragma GCC optimize("Ofast","O3")
#pragma GCC target("avx","avx2")
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long 
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=1000005;
const int mod=1e6+3;
const int INF=1e7;
struct segtree{
    int v[N<<2];
    void pull(int id){
        v[id]=min(v[id<<1],v[id<<1|1]);
    }
    void add(int id,int l,int r,int p,int x){
        if(r-l==1){
            v[id]=x;
            return;
        }
        int m=(l+r)>>1;
        if(p<m)add(id<<1,l,m,p,x);
        else add(id<<1|1,m,r,p,x);
        pull(id);
    }
    int ask(int id,int l,int r,int a,int b){
        if(a<=l&&b>=r)return v[id];
        int m=(l+r)>>1;
        if(b<=m)return ask(id<<1,l,m,a,b);
        if(a>=m)return ask(id<<1|1,m,r,a,b);
        return min(ask(id<<1,l,m,a,b),ask(id<<1|1,m,r,a,b));
    }
}st;
int32_t main(){
    LCBorz;
    int n;cin>>n;
    vector<int> v(n+2),pre(n+2),suf(n+2);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    for(int i=1;i<=n;i++){
        pre[i]=max(pre[i-1],v[i]);
    }
    for(int i=n;i>=1;i--){
        suf[i]=max(suf[i+1],v[i]);
    }
    for(int i=1;i<=n;i++){
        st.add(1,1,n+1,i,v[i]);
    }
    ll ans=0;
    for(int val=1;val<=100;val++){
        vector<int> t;
        for(int j=1;j<=n;j++){
            if(v[j]<=val){
                st.add(1,1,n+1,j,INF);
            }
            if(min(pre[j],suf[j])>v[j]&&v[j]==val){
                t.push_back(j);
            }
        }
        for(int j:t){
            v[j]++;
        }
        int m=t.size();
        if(m==0){
            continue;
        }
        if(m==1){
            ans+=val+st.ask(1,1,n+1,1,t[0])+st.ask(1,1,n+1,t[0]+1,n+1);
            ans%=mod;
            //cout<<ans<<endl;
            continue;
        }
        int tmp=st.ask(1,1,n+1,1,t[0])+st.ask(1,1,n+1,t[0]+1,n+1)+val+(val+1)+val+st.ask(1,1,n+1,t[m-1]+1,n+1);
        int tmp1=st.ask(1,1,n+1,1,t[m-1])+st.ask(1,1,n+1,t[m-1]+1,n+1)+val+(val+1)+val+st.ask(1,1,n+1,1,t[0]);
        ans+=min(tmp,tmp1);
        ans+=(m-2)*(3*val+2);
        ans%=mod;
    }
    cout<<ans<<endl;
    
    return 0;
}
/*
20
1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 1
4
*/

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 3
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 4