40 | 2021-01-08 20:33:44 | mraron | Fancy Fence | cpp11 | Elfogadva 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 2ms | 1752 KiB | ||||
2 | Elfogadva | 2ms | 1800 KiB | ||||
subtask2 | 12/12 | ||||||
3 | Elfogadva | 1ms | 1864 KiB | ||||
4 | Elfogadva | 1ms | 1864 KiB | ||||
5 | Elfogadva | 1ms | 1876 KiB | ||||
6 | Elfogadva | 1ms | 1872 KiB | ||||
7 | Elfogadva | 1ms | 1880 KiB | ||||
subtask3 | 13/13 | ||||||
8 | Elfogadva | 1ms | 1948 KiB | ||||
9 | Elfogadva | 13ms | 3812 KiB | ||||
10 | Elfogadva | 24ms | 6604 KiB | ||||
11 | Elfogadva | 24ms | 7776 KiB | ||||
12 | Elfogadva | 25ms | 8952 KiB | ||||
subtask4 | 15/15 | ||||||
13 | Elfogadva | 1ms | 6004 KiB | ||||
14 | Elfogadva | 4ms | 6460 KiB | ||||
15 | Elfogadva | 16ms | 8492 KiB | ||||
16 | Elfogadva | 30ms | 12080 KiB | ||||
17 | Elfogadva | 30ms | 14160 KiB | ||||
subtask5 | 15/15 | ||||||
18 | Elfogadva | 2ms | 11232 KiB | ||||
19 | Elfogadva | 4ms | 12364 KiB | ||||
20 | Elfogadva | 24ms | 15160 KiB | ||||
21 | Elfogadva | 34ms | 21532 KiB | ||||
22 | Elfogadva | 32ms | 23404 KiB | ||||
subtask6 | 18/18 | ||||||
23 | Elfogadva | 1ms | 16164 KiB | ||||
24 | Elfogadva | 1ms | 16216 KiB | ||||
25 | Elfogadva | 2ms | 16220 KiB | ||||
26 | Elfogadva | 2ms | 16264 KiB | ||||
27 | Elfogadva | 1ms | 16236 KiB | ||||
subtask7 | 27/27 | ||||||
28 | Elfogadva | 6ms | 16684 KiB | ||||
29 | Elfogadva | 8ms | 16880 KiB | ||||
30 | Elfogadva | 24ms | 18792 KiB | ||||
31 | Elfogadva | 24ms | 19804 KiB | ||||
32 | Elfogadva | 28ms | 23112 KiB | ||||
33 | Elfogadva | 28ms | 24868 KiB | ||||
34 | Elfogadva | 32ms | 26876 KiB | ||||
35 | Elfogadva | 28ms | 28816 KiB | ||||
36 | Elfogadva | 1ms | 25888 KiB | ||||
37 | Elfogadva | 28ms | 30768 KiB | ||||
38 | Elfogadva | 28ms | 32752 KiB | ||||
39 | Elfogadva | 29ms | 35576 KiB | ||||
40 | Elfogadva | 32ms | 38900 KiB |