Submission #946347

#TimeUsernameProblemLanguageResultExecution timeMemory
946347XiaoyangFancy Fence (CEOI20_fancyfence)C++17
0 / 100
4 ms4764 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define fi first #define se second #define pll pair<ll,ll> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl; #define MP make_pair #define rep(i,a,b) for(ll i=a;i<b;i++) #define SZ(x) (ll)x.size() #define ALL(x) x.begin(),x.end() #define endl "\n" const ll inf=1e18; ll lowbit(ll x){return x&(-x);} const ll mod=1e9+7; ll c2(ll x){ return (x*(x-1)/2)%mod; } ll rect(ll x,ll y){ ll xx=(x*(x+1)/2)%mod; ll yy=(y*(y+1)/2)%mod; return (xx*yy)%mod; } const ll maxn=1e5+5; ll h[maxn],w[maxn],pre[maxn]; ll inc(ll &a,ll b){return a=(a+b)%mod;} ll dec(ll &a,ll b){return a=(a-b+mod)%mod;} int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n;cin>>n; ll tot=0,ans=0; rep(i,1,n+1)cin>>h[i]; rep(i,1,n+1){ cin>>w[i],inc(tot,w[i]); pre[i]=pre[i-1]+w[i]; } stack<pll>s; //monotonically increasing stack s.push(MP(0ll,0ll)); rep(i,1,n+1){ while(!s.empty() and s.top().se>h[i])s.pop(); ll len=(pre[i-1]-pre[s.top().se]+mod)%mod; inc(ans,(((c2(h[i]+1)*len)%mod)*w[i])%mod); inc(ans,(s.top().se*w[i])%mod); inc(ans,rect(h[i],w[i])); s.push(MP(i,(c2(h[i]+1)*(w[i]))%mod)); } cout<<ans<<endl; 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...