Submission #982590

#TimeUsernameProblemLanguageResultExecution timeMemory
982590MighilonFancy Fence (CEOI20_fancyfence)C++17
27 / 100
19 ms4068 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "../Library/debug.h" #else #define dbg(x...) // #define cin fin // #define cout fout // const string FILE_NAME = ""; ifstream fin(FILE_NAME + ".in"); ofstream fout(FILE_NAME + ".out"); #endif typedef long long ll; typedef long double ld; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i) #define trav(a, x) for (auto& a : x) #define f first #define s second #define pb push_back #define sz(x) (int)(x).size() #define all(x) x.begin(), x.end() const char nl = '\n'; const int INF = 1e9; const ll MOD = 1e9 + 7; const int mxN = 1e6 + 1; ll mul(ll a, ll b){ return (ll) a * b % MOD; } const ll INV_TWO = (MOD + 1) / 2; ll half(ll a){ return mul(a, INV_TWO); } void add_self(ll& a, ll b){ a += b; if(a >= MOD) a -= MOD; } ll f(ll a){ return half(mul(a, a + 1)); } void solve(){ int n; cin >> n; vl h(n + 1), w(n + 1); F0R(i, n) cin >> h[i]; F0R(i, n) cin >> w[i]; h[n] = 0; w[n] = 0; // h, totalw; stack<array<ll, 2>> st; ll ans = 0; FOR(i, 0, n + 1){ ll w_left = 0; while(!st.empty() && st.top()[0] >= h[i]){ add_self(w_left, st.top()[1]); add_self(ans, mul(f(st.top()[0]), f(w_left))); add_self(ans, -mul(f(st.top()[0]), f(w_left - st.top()[1]))); st.pop(); } dbg(i, w_left, h[i], w[i]); dbg(ans); if(w_left != 0){ add_self(ans, -mul(f(h[i]), f(w_left))); } dbg(ans); st.push({h[i], w[i] + w_left}); } cout << ans << nl; } int32_t main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int TC = 1; /* cin >> TC; */ while(TC--){ 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...