Untitled
unknown
c_cpp
a year ago
2.0 kB
2
Indexable
Never
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif constexpr int MOD = 998244353; void md(long long &n) { n = (n % MOD + MOD) % MOD; } void solve() { int n; cin >> n; vector<long long> a(n); for (long long &i : a) cin >> i; vector<long long> dmx(n + 1), dmn(n + 1), pdp(n + 2); dmx[0] = 1; dmn[0] = 0; pdp[1] = 1; vector<pair<int, int>> mx, mn; mx.emplace_back(INT_MAX, 0); mn.emplace_back(INT_MIN, 0); for (int i = 1; i <= n; i++) { while (a[i - 1] >= mx.back().first) { mx.pop_back(); } debug(mx); for (int j = i - 1; j >= mx.back().second; j--) { debug(j, dmx[j] - dmn[j], a[i - 1]); dmx[i] += (dmx[j] - dmn[j]) * a[i - 1]; md(dmx[i]); } for (int j = mx.size() - 1; j >= 1; j--) { debug(j); for (int c = mx[j - 1].second; c < mx[j].second; c++) { debug(c); dmx[i] += (dmx[c] - dmn[c]) * mx[j].first; md(dmx[i]); } } mx.emplace_back(a[i - 1], i); while (a[i - 1] <= mn.back().first) { mn.pop_back(); } for (int j = i - 1; j >= mn.back().second; j--) { dmn[i] += (dmx[j] - dmn[j]) * a[i - 1]; md(dmn[i]); } for (int j = mn.size() - 1; j >= 1; j--) { for (int c = mn[j - 1].second; c < mn[j].second; c++) { dmn[i] += (dmx[c] - dmn[c]) * mn[j].first; md(dmn[i]); } } mn.emplace_back(a[i - 1], i); } debug(dmx); debug(dmn); long long ans = dmx[n] - dmn[n]; md(ans); cout << ans; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { solve(); } return 0; }