Submission #1182025

#TimeUsernameProblemLanguageResultExecution timeMemory
1182025AlgorithmWarriorFancy Fence (CEOI20_fancyfence)C++20
100 / 100
49 ms2376 KiB
#include <bits/stdc++.h> using namespace std; int const MAX=100005; int const MOD=1000000007; int const INV2=500000004; int h[MAX],w[MAX]; int n; int ans; struct info{ int len,h,total; }; void read(){ cin>>n; int i; for(i=1;i<=n;++i) cin>>h[i]; for(i=1;i<=n;++i) cin>>w[i]; } void aduna(int& x,int val){ x=(x+val)%MOD; } void solve(){ stack<info>stv; int i; for(i=1;i<=n;++i){ aduna(ans,1LL*w[i]*(w[i]+1)%MOD*INV2%MOD*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD); int len=0; while(!stv.empty() && stv.top().h>h[i]){ aduna(len,stv.top().len); stv.pop(); } aduna(ans,1LL*w[i]*len%MOD*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD); if(!stv.empty()) aduna(ans,1LL*w[i]*stv.top().total%MOD); aduna(len,w[i]); int total=1LL*len*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD; if(!stv.empty()) aduna(total,stv.top().total); stv.push({len,h[i],total}); } } int main() { read(); solve(); cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...