Submission #1192151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192151		Aiperiii	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	19 ms	6656 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
const int mod=1e9+7;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    
    vector <int> h(n),w(n);
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    int ans=0;
    h.pb(0);
    w.pb(0);
    stack <int> sth,stw;
    sth.push(0);
    stw.push(0);
    
    for(int i=0;i<n+1;i++){
        if(h[i]>=sth.top()){
            sth.push(h[i]);
            stw.push(w[i]);
        }
        else{
            vector <int> v;
            vector <int> v2;
            int sum=0;
            while(sth.top()>h[i]){
                v.pb(sth.top());
                sth.pop();
                v2.pb(stw.top());
                sum+=stw.top();
                stw.pop();
            }
            sth.push(h[i]);
            stw.push(sum+w[i]);
            
            int x=(h[i]*(h[i]+1)/2)%mod;
            int y=((sum%mod)*((sum+1)%mod)/2)%mod;
            x*=y;
            
            x%=mod;
            ans+=mod;
            ans-=x;
            ans%=mod;
            v.pb(0);
            v2.pb(0);
            for(int j=v.size()-2;j>=0;j--){
                int x=v[j];
                int y=sum%mod;
                x*=(x+1);
                x/=2;
                y*=(y+1)%mod;
                y/=2;
                x%=mod;
                y%=mod;
                
                int c=(x*y)%mod;
                x=v[j+1];
                x*=(x+1);
                x/=2;
                x%=mod;
                c+=mod;
                c-=(x*y)%mod;
                c%=mod;
                ans+=c;
                ans%=mod;
                
                //cout<<c<<" ";
                sum-=v2[j];
                //cout<<v2[j]<<"\n";
            }
            
        }
    }
    cout<<ans<<"\n";
}
/*
 10^14*(10^14+1)/2
*/

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27