Submission #577550

#TimeUsernameProblemLanguageResultExecution timeMemory
577550talant117408Fancy Fence (CEOI20_fancyfence)C++17
30 / 100
56 ms3532 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' void solve() { int n; cin >> n; ll mod = 1e9+7; function <ll(ll, ll)> add = [&](ll a, ll b) { return ((a+b)%mod+mod)%mod; }; function <ll(ll, ll)> mult = [&](ll a, ll b) { return ((a*b)%mod+mod)%mod; }; function <ll(ll, ll)> binpow = [&](ll a, ll b) { ll res = 1; while (b) { if (b&1) res = mult(res, a); a = mult(a, a); b >>= 1; } return res; }; ll inv2 = binpow(2, mod-2); function <ll(ll)> calc = [&](ll n) { return mult(mult(n, n+1), inv2); }; vector <ll> h(n), w(n); for (auto &to : h) cin >> to; for (auto &to : w) cin >> to; stack <pll> heights; ll ans = 0, sum = 0; for (int i = 0; i < n; i++) { ll left = 0; while (sz(heights) && heights.top().first > h[i]) { auto v = heights.top(); heights.pop(); left = add(left, v.second); sum = add(sum, -mult(calc(v.first), v.second)); } ans = add(ans, -mult(calc(h[i]), calc(left))); ans = add(ans, mult(calc(h[i]), calc(w[i]+left))); ans = add(ans, mult(sum, add(w[i], left))); sum = add(sum, mult(calc(h[i]), add(w[i], left))); heights.push(mp(h[i], add(w[i], left))); } cout << ans << endl; } int main() { do_not_disturb int t = 1; //~ cin >> t; while (t--) { solve(); } 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...