제출 #1006905

#제출 시각아이디문제언어결과실행 시간메모리
1006905HanksburgerFancy Fence (CEOI20_fancyfence)C++17
27 / 100
18 ms1956 KiB
#include <bits/stdc++.h> using namespace std; long long h[100005], w[100005], mod=1e9+7, inv2=5e8+4; vector<pair<long long, long long> > vec; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n, cur=0, ans=0; cin >> n; for (long long i=1; i<=n; i++) cin >> h[i]; for (long long i=1; i<=n; i++) cin >> w[i]; vec.push_back({-1, 0}); vec.push_back({0, 0}); for (long long i=1; i<=n+1; i++) { while (vec[vec.size()-2].first>=h[i]) { long long x=(cur-vec[vec.size()-1].second+mod)*(cur-vec[vec.size()-1].second+1+mod)%mod*inv2%mod; long long y=(vec[vec.size()-1].first+vec[vec.size()-2].first+1)*(vec[vec.size()-1].first-vec[vec.size()-2].first+mod)%mod*inv2%mod; ans+=x*y%mod; vec.pop_back(); } if (vec[vec.size()-1].first>h[i]) { long long x=(cur-vec[vec.size()-1].second+mod)*(cur-vec[vec.size()-1].second+1+mod)%mod*inv2%mod; long long y=(vec[vec.size()-1].first+h[i]+1)*(vec[vec.size()-1].first-h[i]+mod)%mod*inv2%mod; ans+=x*y%mod; vec[vec.size()-1].first=h[i]; } else vec.push_back({h[i], cur}); cur=(cur+w[i])%mod; } cout << ans; }
#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...