結果
| 問題 | No.3812 Max Min Sigma Problem |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-20 22:27:00 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 503 ms / 2,000 ms |
| + 178µs | |
| コード長 | 5,247 bytes |
| 記録 | |
| コンパイル時間 | 2,170 ms |
| コンパイル使用メモリ | 239,648 KB |
| 実行使用メモリ | 49,572 KB |
| 最終ジャッジ日時 | 2026-11-20 22:28:18 |
| 合計ジャッジ時間 | 7,322 ms |
|
ジャッジサーバーID (参考情報) |
judge3_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
// https://github.com/potato167/po167_library
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include <atcoder/segtree>
#include <atcoder/lazysegtree>
ll op(ll a, ll b) {
return min(a, b);
}
ll e() {
return INF;
}
ll target;
bool f(ll x) {
return x > target;
}
struct lazy_S {
ll val;
ll size;
};
using lazy_F = ll;
lazy_S lazy_op(lazy_S l, lazy_S r) {
return lazy_S{
l.val + r.val,
l.size + r.size
};
}
lazy_S lazy_e() { return lazy_S{0, 0}; }
lazy_S mapping(lazy_F l, lazy_S r) {
if (l == -1) return r;
r.val = r.size * l;
return r;
}
//l(r(x))
lazy_F composition(lazy_F l, lazy_F r) {
if (l == -1) return r;
return l;
}
lazy_F lazy_id(){return -1;}
#define lazy_calc lazy_S,lazy_op,lazy_e,lazy_F,mapping,composition,lazy_id
void solve();
// DEAR MYSTERIES / TOMOO
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
rep(i, 0, t) solve();
}
void solve(){
int N;
cin >> N;
vector<ll> A(N);
rep(i, 0, N) cin >> A[i];
mint ans = 0;
vector<int> L(N), R(N);
rep(rp, 0, 2) {
atcoder::segtree<ll, op, e> seg(A);
rep(i, 0, N) {
target = A[i] - 1;
L[i] = seg.min_left<f>(i);
target = A[i];
R[i] = seg.max_right<f>(i + 1);
mint tmp = A[i] * A[i];
tmp *= i + 1 - L[i];
tmp *= R[i] - i;
ans += tmp;
// cout << A[i] << " " << tmp.val() << " " << L[i] << " " << R[i] << endl;;
}
rep(i, 0, N) A[i] *= -1;
}
vector<int> B(N);
rep(i, 0, N) {
if (L[i] + R[i] < i * 2) B[i] = 1;
}
// cout << ans.val() << "\n";
ans /= 2;
rep(rp, 0, 2) {
reverse(all(L));
reverse(all(R));
reverse(all(A));
reverse(all(B));
atcoder::segtree<ll, op, e> seg(A);
rep(i, 0, N) {
L[i] = N - L[i];
R[i] = N - R[i];
}
swap(L, R);
atcoder::lazy_segtree<lazy_calc> ls(vector<lazy_S>(N, {0, 1}));
rep(i, 0, N) {
target = A[i];
int l = seg.min_left<f>(i);
ls.apply(l, i + 1, A[i]);
if (B[i] == rp) {
int r = i;
while (r < R[i]) {
target = A[r] - 1;
int nr = min(seg.max_right<f>(r), R[i]);
l = max(L[i], seg.min_left<f>(i));
mint tmp = 0;
tmp += mint(ls.prod(L[i], l).val);
tmp += (mint(A[r])) * (i + 1 - l);
tmp *= (nr - r);
ans -= tmp * A[i];
// cout << rp << " " << A[i] << " " << l << " " << r << " " << nr << " " << tmp.val() << endl;
r = nr;
}
}
}
}
ans *= 2;
cout << ans.val() << "\n";
return;
{
mint ans2 = 0;
rep(l, 0, N) rep(r, l + 1, N + 1) {
ll a = INF, b =0;
rep(i, l, r) {
chmin(a, A[i]);
chmax(b, A[i]);
}
ans2 += square(a - b);
}
cout << ans2.val() << endl;
if (ans != ans2) {
for (auto x : A) {
cerr << x << " ";
}
cerr << endl;
assert(false);
}
}
}
/*
*
* 最大値の2乗の和とかは簡単
* 最大値を左から順に見ていき、
* prefix min を適時更新する
*
* log2個とかでは解けたがすごい大変だ
*
*/