結果
問題 | No.2950 Max Min Product |
ユーザー | 👑 binap |
提出日時 | 2024-10-26 07:06:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 223 ms / 3,000 ms |
コード長 | 4,392 bytes |
コンパイル時間 | 12,006 ms |
コンパイル使用メモリ | 267,348 KB |
実行使用メモリ | 8,048 KB |
最終ジャッジ日時 | 2024-10-26 07:07:21 |
合計ジャッジ時間 | 13,359 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 137 ms
6,816 KB |
testcase_04 | AC | 152 ms
6,844 KB |
testcase_05 | AC | 141 ms
6,824 KB |
testcase_06 | AC | 199 ms
8,044 KB |
testcase_07 | AC | 199 ms
8,044 KB |
testcase_08 | AC | 223 ms
7,916 KB |
testcase_09 | AC | 100 ms
6,816 KB |
testcase_10 | AC | 170 ms
7,388 KB |
testcase_11 | AC | 150 ms
6,820 KB |
testcase_12 | AC | 198 ms
7,920 KB |
testcase_13 | AC | 196 ms
8,048 KB |
testcase_14 | AC | 197 ms
8,044 KB |
testcase_15 | AC | 188 ms
7,588 KB |
testcase_16 | AC | 133 ms
6,820 KB |
testcase_17 | AC | 149 ms
6,852 KB |
testcase_18 | AC | 193 ms
8,044 KB |
testcase_19 | AC | 200 ms
8,044 KB |
testcase_20 | AC | 201 ms
8,044 KB |
testcase_21 | AC | 137 ms
6,816 KB |
testcase_22 | AC | 149 ms
6,816 KB |
testcase_23 | AC | 101 ms
6,820 KB |
testcase_24 | AC | 199 ms
8,048 KB |
testcase_25 | AC | 198 ms
7,880 KB |
testcase_26 | AC | 203 ms
7,876 KB |
testcase_27 | AC | 137 ms
6,816 KB |
testcase_28 | AC | 217 ms
7,740 KB |
testcase_29 | AC | 138 ms
6,816 KB |
testcase_30 | AC | 194 ms
7,916 KB |
testcase_31 | AC | 204 ms
8,044 KB |
testcase_32 | AC | 200 ms
7,920 KB |
testcase_33 | AC | 156 ms
6,816 KB |
testcase_34 | AC | 106 ms
6,820 KB |
testcase_35 | AC | 154 ms
6,816 KB |
testcase_36 | AC | 216 ms
8,044 KB |
testcase_37 | AC | 213 ms
7,920 KB |
testcase_38 | AC | 210 ms
7,916 KB |
testcase_39 | AC | 2 ms
6,820 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using namespace atcoder; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef long double ld; typedef pair<int, int> P; template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;} template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;} template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;} template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;} template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;} template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;} template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;} template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template<typename T> void chmin(T& a, T b){a = min(a, b);} template<typename T> void chmax(T& a, T b){a = max(a, b);} using mint = modint998244353; int main(){ int n; cin >> n; vector<int> a(n); cin >> a; mint ans = 0; auto dfs = [&](auto self, int left, int right) -> void { if(right == left + 1){ ans += mint(a[left]) * a[left]; return; } int mid = (right + left) / 2; self(self, left, mid); self(self, mid, right); int ln = mid - left; int rn = right - mid; vector<long long> lmax(ln); vector<long long> lmin(ln); vector<long long> rmax(rn); vector<long long> rmin(rn); { int tmp = 0; rep(i, ln){ int idx = (mid - 1) - i; chmax(tmp, a[idx]); lmax[i] = tmp; } } { int tmp = 1001001001; rep(i, ln){ int idx = (mid - 1) - i; chmin(tmp, a[idx]); lmin[i] = tmp; } } { int tmp = 0; rep(i, rn){ int idx = mid + i; chmax(tmp, a[idx]); rmax[i] = tmp; } } { int tmp = 1001001001; rep(i, rn){ int idx = mid + i; chmin(tmp, a[idx]); rmin[i] = tmp; } } vector<mint> lmax_sum(ln + 1); vector<mint> rmax_sum(rn + 1); rep(li, ln) lmax_sum[li + 1] = lmax_sum[li] + lmax[li]; rep(ri, rn) rmax_sum[ri + 1] = rmax_sum[ri] + rmax[ri]; /* cout << lmax; cout << lmin; cout << rmax; cout << rmin; */ int li = 0; int ri = 0; mint plus = 0; auto right_up = [&](){ int idx = upper_bound(lmax.begin(), lmax.end(), rmax[ri]) - lmax.begin(); if(idx <= li) plus += (mint)(rmax[ri] * idx + (lmax_sum[li] - lmax_sum[idx])) * rmin[ri]; else plus += (mint)(rmax[ri] * li) * rmin[ri]; ri++; }; auto left_up = [&](){ int idx = upper_bound(rmax.begin(), rmax.end(), lmax[li]) - rmax.begin(); if(idx <= ri) plus += (mint)(lmax[li] * idx + (rmax_sum[ri] - rmax_sum[idx])) * lmin[li]; else plus += (mint)(lmax[li] * ri) * lmin[li]; li++; }; while(li < ln or ri < rn){ if(li == ln){ right_up(); continue; } if(ri == rn){ left_up(); continue; } if(lmin[li] < rmin[ri]){ right_up(); }else{ left_up(); } } ans += plus; // cout << plus << "\n"; }; dfs(dfs, 0, n); cout << ans << "\n"; return 0; }