oj.uz

Submission #477480

# Submission time Handle Problem Language Result Execution time Memory
477480 2021-10-02T09:20:45 Z niloyroot Fancy Fence (CEOI20_fancyfence) C++14
25 / 100
 22 ms 6608 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vi = vector<ll>;
using ml = map<ll,ll>;
const ll mod=1000000007;
#define pb push_back
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define newl '\n'
#define form(m,it) for(auto it=m.begin();it!=m.end(); it++)
#define ff first
#define ss second

void solve(){
    ll n; cin>>n;
    ll h[n+1],w[n+1];
    forp(i,1,n){cin>>h[i];}
    forp(i,1,n){cin>>w[i];}
    ll dp[n+1],m[n+1],pre[n+1];
    stack<pl> st;
    st.push({0,0}); 
    dp[0]=pre[0]=h[0]=w[0]=0;
    forp(i,1,n){
        pre[i]=pre[i-1]+w[i]; pre[i]%=mod;
        while(st.top().ff>h[i]){
            st.pop();
        }
        m[i]=st.top().second;
        st.push({h[i],i});
    }
    ll ans=0,j,c,d;
    forp(i,1,n){
        j=m[i];
        dp[i]=dp[j];
        c=(h[i]*(h[i]+1))/2; c%=mod; c*=(pre[i]-pre[j]); c%=mod;
        dp[i]+=c; dp[i]%=mod;
        c=(h[i]*(h[i]+1))/2; c%=mod; c*=(w[i]*(w[i]-1))/2; c%=mod;
        d=(h[i]*(h[i]+1))/2; d%=mod; d*=(w[i]-1); d%=mod; d*=(pre[i-1]-pre[j]); d%=mod;
        c+=d; c%=mod;
        ans+=c; ans%=mod;
        ans+=(dp[j]*(w[i]-1)); ans%=mod;
        ans+=dp[i]; ans%=mod;
    }
    cout<<(ans+mod)%mod<<newl;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 208 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 11 ms 3088 KB Output is correct
4 Correct 22 ms 6608 KB Output is correct
5 Correct 22 ms 5996 KB Output is correct
6 Correct 22 ms 5456 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct