Submission #1008112

#TimeUsernameProblemLanguageResultExecution timeMemory
1008112kebineFancy Fence (CEOI20_fancyfence)C++17
0 / 100
3 ms4812 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<ll,ll> #define REP(i,x,y) for(ll i=x;i<=y;i++) #define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #define mod 1000000007 #define pb push_back #define mk make_pair #define ll long long #define foor(x,vec) for(auto x:vec ){cout<<x<<" ";} #define fi first #define se second #define MAXN 700069 #define lld long double #define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ffl fflush(stdout) #define sst string #define pii pair<ll,ll> ll mvx[]={0,0,-1,1}; ll mvy[]={1,-1,0,0}; ll n,q; ll a,b; ll h[MAXN],w[MAXN]; ll ps[MAXN]; ll dp[MAXN]; ll idx[MAXN]; ll mul(ll a,ll b){ a=a%mod; b=b%mod; a*=b; a%=mod; return a; } int main(){ cin>>n; REP(i,1,n)cin>>h[i]; REP(i,1,n)cin>>w[i]; REP(i,1,n){ ps[i]=ps[i-1]+w[i]; } stack <ll> stck; stck.push(0); REP(i,1,n){ while(stck.size() && h[i]<stck.top()){ stck.pop(); } idx[i]=stck.top(); stck.push(h[i]); } ll ans=0; REP(i,1,n){ ll val=(dp[idx[i]])%mod*(ps[i]-ps[idx[i]]); val%=mod; val=val+mul(h[i]*(h[i]+1)/2,w[i]*(w[i]+1)/2)%mod; val%=mod; val=val+mul(mul(h[i],h[i]+1)/2,(ps[i-1]-ps[idx[i]]))%mod; ans+=val; ans%=mod; dp[i]=dp[idx[i]]+mul(mul(h[i],h[i]+1)/2,(ps[i]-ps[idx[i]])); dp[i]%=mod; } cout<<ans<<endl; }
#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...