Submission #856411

#TimeUsernameProblemLanguageResultExecution timeMemory
856411NiktopFancy Fence (CEOI20_fancyfence)C++14
12 / 100
1 ms2396 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define mii map<int,int> #define F first #define S second #define pb push_back #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #pragma GCC optimize ("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize ("-O2") const int N = 1e5+5, mod = 1e9+7; int h[N], w[N], ans[N], ps[N]; vector <int> v; int inv2; int pw(int a, int b) { if (b == 0) return 1; if (b % 2 == 1) return ((pw(a * a % mod, b/2) % mod) * a) % mod; return pw(a * a % mod, b/2) % mod; } int c2(int x) { x %= mod; return (((x * (x-1)) % mod) * inv2) % mod; } int tr(int hr, int wr) { if (hr == 0 || wr == 0) return 0; int a; a = c2(hr * wr) + (hr * c2(wr)) % mod + (wr * c2(hr)) % mod; a = (a * inv2) % mod; return (a + hr * wr)%mod; } int32_t main() { int n; cin >> n; inv2 = pw(2,mod-2); for (int i = 1; i <= n; i++) cin >> h[i]; for (int i = 1; i <= n; i++) cin >> w[i], ps[i] = ps[i-1] + w[i]; h[0] = 0; v.pb(0); int sum = 0; for (int i = 1; i <= n; i++) { while (h[v[v.size()-1]]>=h[i]) v.pop_back(); int j = v[v.size()-1]; v.pb(i); int tw = ps[i] - ps[j]; ans[i] = (tr(tw,h[i]) - tr(tw-w[i],h[i])+mod); ans[i] += (w[i]*ans[j])%mod; ans[i] %= mod; sum += ans[i]; sum %= mod; } cout << sum << 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...