40 | 2021-01-08 20:33:44 | mraron | Fancy Fence | cpp11 | Accepted 100/100 | 34ms | 38900 KiB |
//fancyfence lineáris
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const ll inv2=500000004;
#define xx first
#define yy second
int main() {
ios_base::sync_with_stdio(false);
int n;
cin>>n;
vector<ll> h(n), w(n);
for(int i=0;i<n;++i) cin>>h[i];
for(int i=0;i<n;++i) cin>>w[i];
vector<pair<ll,ll>> t; //(height, width)
t.push_back({0,0});
ll ans=0;
for(int i=0;i<n;++i) {
ll wlen=0;
while(t.back().xx>h[i]) {
ll prev=max(h[i],t[(int)t.size()-2].xx);
ll hdiff=t.back().xx-prev;
wlen=(wlen+t.back().yy)%mod;
t.pop_back();
ans+=(hdiff*(hdiff+1)%mod*inv2%mod+hdiff*prev%mod)*(wlen*(wlen+1)%mod*inv2%mod)%mod;
ans%=mod;
}
if(t.back().xx==h[i]) {
t.back().yy=(t.back().yy+wlen+w[i])%mod;
}else {
t.push_back({h[i], (wlen+w[i])%mod});
}
}
while((int)t.size()>1) {
pair<ll,ll> akt=t.back();t.pop_back();
ll hdiff=akt.xx-t.back().xx;
ans+=(hdiff*(t.back().xx)%mod+hdiff*(hdiff+1)%mod*inv2%mod)*(akt.yy*(akt.yy+1)%mod*inv2%mod)%mod;
ans%=mod;
t.back().yy+=akt.yy;
t.back().yy%=mod;
}
cout<<ans<<"\n";
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 2ms | 1752 KiB | ||||
2 | Accepted | 2ms | 1800 KiB | ||||
subtask2 | 12/12 | ||||||
3 | Accepted | 1ms | 1864 KiB | ||||
4 | Accepted | 1ms | 1864 KiB | ||||
5 | Accepted | 1ms | 1876 KiB | ||||
6 | Accepted | 1ms | 1872 KiB | ||||
7 | Accepted | 1ms | 1880 KiB | ||||
subtask3 | 13/13 | ||||||
8 | Accepted | 1ms | 1948 KiB | ||||
9 | Accepted | 13ms | 3812 KiB | ||||
10 | Accepted | 24ms | 6604 KiB | ||||
11 | Accepted | 24ms | 7776 KiB | ||||
12 | Accepted | 25ms | 8952 KiB | ||||
subtask4 | 15/15 | ||||||
13 | Accepted | 1ms | 6004 KiB | ||||
14 | Accepted | 4ms | 6460 KiB | ||||
15 | Accepted | 16ms | 8492 KiB | ||||
16 | Accepted | 30ms | 12080 KiB | ||||
17 | Accepted | 30ms | 14160 KiB | ||||
subtask5 | 15/15 | ||||||
18 | Accepted | 2ms | 11232 KiB | ||||
19 | Accepted | 4ms | 12364 KiB | ||||
20 | Accepted | 24ms | 15160 KiB | ||||
21 | Accepted | 34ms | 21532 KiB | ||||
22 | Accepted | 32ms | 23404 KiB | ||||
subtask6 | 18/18 | ||||||
23 | Accepted | 1ms | 16164 KiB | ||||
24 | Accepted | 1ms | 16216 KiB | ||||
25 | Accepted | 2ms | 16220 KiB | ||||
26 | Accepted | 2ms | 16264 KiB | ||||
27 | Accepted | 1ms | 16236 KiB | ||||
subtask7 | 27/27 | ||||||
28 | Accepted | 6ms | 16684 KiB | ||||
29 | Accepted | 8ms | 16880 KiB | ||||
30 | Accepted | 24ms | 18792 KiB | ||||
31 | Accepted | 24ms | 19804 KiB | ||||
32 | Accepted | 28ms | 23112 KiB | ||||
33 | Accepted | 28ms | 24868 KiB | ||||
34 | Accepted | 32ms | 26876 KiB | ||||
35 | Accepted | 28ms | 28816 KiB | ||||
36 | Accepted | 1ms | 25888 KiB | ||||
37 | Accepted | 28ms | 30768 KiB | ||||
38 | Accepted | 28ms | 32752 KiB | ||||
39 | Accepted | 29ms | 35576 KiB | ||||
40 | Accepted | 32ms | 38900 KiB |