Submission #1008282

#TimeUsernameProblemLanguageResultExecution timeMemory
1008282andecaandeciFancy Fence (CEOI20_fancyfence)C++17
100 / 100
66 ms10668 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 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]; const ll mod =1e9+7; ll add(ll x, ll y) { ll res=(x+y+mod)%mod; return res; } ll cal(ll x) { return (ll)((1ll * x * (x + 1) / 2) % mod); } ll mult(ll x, ll y) { return (ll)((1ll * x * y) % mod); } 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]; ps[i]%=mod; } vector<ll> stck; ll ans=0; stck.pb(0); for(int i = 1; i <= n; i++) { while(stck.size() && h[i] < h[stck.back()]) { stck.pop_back(); } if(stck.size()) idx[i] = stck.back(); stck.pb(i); } REP(i,1,n) { dp[i] = add(dp[idx[i]], mult((ps[i] - ps[idx[i]]), cal(h[i] ) )); ll val = mult(dp[idx[i]], w[i]); val = add(val, mult( (ps[i - 1]- ps[idx[i]]), mult(w[i], cal(h[i] ) ) ) ); val = add(val, mult(cal(w[i] ), cal(h[i]))); ans = add(ans, val); } ans=(ans+mod)%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...