Submission #999349

#TimeUsernameProblemLanguageResultExecution timeMemory
999349yoav_sFancy Fence (CEOI20_fancyfence)C++17
100 / 100
22 ms7260 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> v; typedef vector<v> vv; typedef vector<vv> vvv; typedef pair<ll,ll> p; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef pair<ll, p> tri; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; #define f first #define s second #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() const ll INF = 1e18; const ll mod = 1e9 + 7; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll N; cin >> N; vp ranges(N); for (ll i= 0; i < N; i++) cin >> ranges[i].f; for (ll i = 0; i < N; i++) cin >> ranges[i].s; v leftGeq(N, -1), rightG(N, N); stack<p> s; for (ll i = 0; i < N; i++) { while (!s.empty() && s.top().f > ranges[i].f) s.pop(); if (!s.empty()) leftGeq[i] = s.top().s; s.emplace(ranges[i].f, i); } s = stack<p>(); for (ll i = N - 1; i >= 0; i--) { while (!s.empty() && s.top().f >= ranges[i].f) s.pop(); if (!s.empty()) rightG[i] = s.top().s; s.emplace(ranges[i].f, i); } v widthPref(N + 1, 0); for (ll i = 1; i <= N; i++) widthPref[i] = (widthPref[i - 1] + ranges[i - 1].s) % mod; ll res = 0; for (ll i = 0; i < N; i++) { ll leftCnt = (widthPref[i] - widthPref[leftGeq[i] + 1] + mod) % mod; ll rightCnt = (widthPref[rightG[i]] - widthPref[i + 1] + mod) % mod; ll meCnt = ranges[i].s; ll intervalCnt = ((leftCnt * rightCnt) % mod) + (((meCnt * (meCnt + 1)) / 2) % mod) + (((leftCnt + rightCnt) * meCnt) % mod); intervalCnt %= mod; ll heightCnt = ranges[i].f * (ranges[i].f + 1) / 2; heightCnt %= mod; res += (intervalCnt * heightCnt) % mod; res %= mod; } cout << res << "\n"; 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...