Submission #610286

#TimeUsernameProblemLanguageResultExecution timeMemory
610286ArnchFancy Fence (CEOI20_fancyfence)C++17
100 / 100
41 ms5192 KiB
// oooo /* har chi delet mikhad bebar ~ gitar o ba khodet nabar! ~ ;Amoo_Hasan; */ #include<bits/stdc++.h> //#pragma GCC optimize("O3,no-stack-protector,unroll-loops") //#pragma GCC target("avx2,fma") using namespace std; typedef long long ll; typedef long double ld; #define Sz(x) int((x).size()) #define All(x) (x).begin(), (x).end() #define wtf(x) cout<<#x <<" : " <<x <<endl constexpr ll inf = 1e18, N = 1e5 + 10, mod = 1e9 + 7, pr = 1000696969; int w[N], h[N]; int l[N], r[N]; ll ps[N], bpow; ll poww(ll x, int y) { ll res = 1; for(; y; y /= 2, x = x * x % mod) if(y & 1) { res *= x; res %= mod; } return res; } ll choose(ll x) { ll ans = (x * (x - 1)) % mod; ans *= bpow; ans %= mod; return ans; } int main() { ios :: sync_with_stdio(0), cin.tie(0); bpow = poww(2, mod - 2); int n; cin >>n; for(int i = 0; i < n; i++) cin >>h[i]; for(int i = 0; i < n; i++) cin >>w[i]; vector<int> vc; for(int i = 0; i < n; i++) { while(!vc.empty() && h[vc.back()] >= h[i]) vc.pop_back(); if(vc.empty()) l[i] = 0; else l[i] = vc.back() + 1; vc.push_back(i); } vc.clear(); for(int i = n - 1; i >= 0; i--) { while(!vc.empty() && h[vc.back()] > h[i]) vc.pop_back(); if(vc.empty()) r[i] = n - 1; else r[i] = vc.back() - 1; vc.push_back(i); } for(int i = 0; i < n; i++) { ps[i] = w[i]; if(i > 0) ps[i] += ps[i - 1]; ps[i] %= mod; } ll ans = 0; for(int i = 0; i < n; i++) { int mx = 0; if(l[i] > 0) mx = max(mx, h[l[i] - 1] + 1); if(r[i] < n - 1) mx = max(mx, h[r[i] + 1] + 1); ll cnt = (choose(h[i] + 1) - choose(mx) + mod) % mod; ll num = ps[r[i]]; if(l[i] > 0) num -= ps[l[i] - 1]; if(num < 0) num += mod; num = choose(num + 1); cnt *= num, cnt %= mod; ans += cnt, ans %= mod; } cout<<ans; 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...