結果
| 問題 | No.3812 Max Min Sigma Problem |
| コンテスト | |
| ユーザー |
kwm_t
|
| 提出日時 | 2026-11-21 14:20:18 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 258 ms / 2,000 ms |
| + 525µs | |
| コード長 | 2,466 bytes |
| 記録 | |
| コンパイル時間 | 4,738 ms |
| コンパイル使用メモリ | 381,540 KB |
| 実行使用メモリ | 21,100 KB |
| 最終ジャッジ日時 | 2026-11-21 14:20:28 |
| 合計ジャッジ時間 | 9,512 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
using mint = modint998244353;
const int mod = 998244353;
const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n; cin >> n;
vector<long long>a(n);
rep(i, n)cin >> a[i];
mint ans = 0;
auto dfs = [&](auto&& dfs, int l, int r) {
if (l + 1 == r) return;
int m = (l + r) / 2;
int lsz = m - l;
int rsz = r - m;
vector<mint> csmin1(rsz + 1);
vector<mint> csmin2(rsz + 1);
vector<mint> csmax1(rsz + 1);
vector<mint> csmax2(rsz + 1);
vector<mint> csmaxmin(rsz + 1);
vector<int>cmin(rsz), cmax(rsz);
{
long long mn = INF, mx = -INF;
rep(i, rsz) {
chmin(mn, a[m + i]);
chmax(mx, a[m + i]);
cmin[i] = mn;
cmax[i] = mx;
csmin1[i + 1] += csmin1[i] + mn;
csmin2[i + 1] += csmin2[i] + mn * mn;
csmax1[i + 1] += csmax1[i] + mx;
csmax2[i + 1] += csmax2[i] + mx * mx;
csmaxmin[i + 1] += csmaxmin[i] + mn * mx;
}
}
{
long long mn = INF, mx = -INF;
int rmax = 0, rmin = 0;
rrep2(i, l, m) {
chmin(mn, a[i]);
chmax(mx, a[i]);
while (rmin < rsz && mn < cmin[rmin]) rmin++;
while (rmax < rsz && cmax[rmax] < mx) rmax++;
// mx * mx
ans += mint(mx) * mx * rmax;
ans += csmax2[rsz] - csmax2[rmax];
// mn * mn
ans += mint(mn) * mn * rmin;
ans += csmin2[rsz] - csmin2[rmin];
// -2 * mn * mx
ans -= mint(2) * mn * mx * min(rmax, rmin);
if (rmax < rmin) {
ans -= mint(2) * mn * (csmax1[rmin] - csmax1[rmax]);
}
else {
ans -= mint(2) * (csmin1[rmax] - csmin1[rmin]) * mx;
}
ans -= mint(2) * (csmaxmin[rsz] - csmaxmin[max(rmax, rmin)]);
}
}
dfs(dfs, l, m);
dfs(dfs, m, r);
};
dfs(dfs, 0, n);
cout << ans.val() << endl;
return 0;
}
kwm_t