結果
問題 | No.1300 Sum of Inversions |
ユーザー | Hyado |
提出日時 | 2020-11-27 22:01:41 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 343 ms / 2,000 ms |
コード長 | 5,364 bytes |
コンパイル時間 | 1,999 ms |
コンパイル使用メモリ | 186,368 KB |
実行使用メモリ | 26,656 KB |
最終ジャッジ日時 | 2024-07-26 12:45:16 |
合計ジャッジ時間 | 11,040 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
//#pragma GCC optimize("Ofast")//#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;using db = double;using ld = long double;template<typename T> using V = vector<T>;template<typename T> using VV = vector<vector<T>>;#define fs first#define sc second#define pb push_back#define mp make_pair#define mt make_tuple#define eb emplace_back#define lb lower_bound#define ub upper_bound#define all(v) (v).begin(),(v).end()#define siz(v) (ll)(v).size()#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)#define ENDL '\n'typedef pair<int,int> Pi;typedef pair<ll,ll> PL;constexpr ll mod = 998244353;constexpr ll INF = 1000000099;constexpr ll LINF = (ll)(1e18 +99);const ld PI = acos((ld)-1);const vector<ll> dx={-1,0,1,0},dy={0,1,0,-1};template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}inline void yes() { cout << "Yes" << ENDL; }inline void no() { cout << "No" << ENDL; }template<typename T,typename Y> inline T mpow(T a, Y n) {T res = 1;for(;n;n>>=1) {if (n & 1) res = res * a;a = a * a;}return res;}template <typename T> V<T> prefix_sum(const V<T>& v) {int n = v.size();V<T> ret(n + 1);rep(i, 0, n) ret[i + 1] = ret[i] + v[i];return ret;}template<typename T>istream& operator >> (istream& is, vector<T>& vec){for(auto&& x: vec) is >> x;return is;}template<typename T,typename Y>ostream& operator<<(ostream& os,const pair<T,Y>& p){return os<<"{"<<p.fs<<","<<p.sc<<"}";}template<typename T> ostream& operator<<(ostream& os,const V<T>& v){os<<"{";for(auto e:v)os<<e<<",";return os<<"}";}template<typename ...Args>void debug(Args&... args){for(auto const& x:{args...}){cerr<<x<<' ';}cerr<<ENDL;}template <long long MOD = mod> // MODを適宜設定することstruct Mint {using M = Mint;ll a;Mint(ll x = 0) {a = x % MOD;if(a < 0) a += MOD;} // MintでM pow(ll n) {M b = *this, r = 1 % MOD;while(n) {if(n & 1) r *= b;b *= b;n >>= 1;}return r;}M inv() { return pow(MOD - 2); }M& operator+=(M r) {a += r.a;if(a >= MOD) a -= MOD;return *this;}M& operator-=(M r) {a += MOD - r.a;if(a >= MOD) a -= MOD;return *this;}M& operator*=(M r) {a = 1LL * a * r.a % MOD;return *this;}M& operator/=(M r) { return (*this) *= r.inv(); }M operator+(M r) const { return M(a) += r; };M operator-(M r) const { return M(a) -= r; };M operator*(M r) const { return M(a) *= r; };M operator/(M r) const { return M(a) /= r; };M operator-() const { return M() - *this; }friend ostream& operator<<(ostream& os, const M& r) { return os << r.a; }};using M = Mint<mod>;/*using M = Mint<mod>;M xとint iの演算はx.a+=i またはx+=M{i}M(x).pow(exp)*/template <typename T> struct BIT {int n;vector<T> bit; // 1-indexedBIT() : n(-1) {}BIT(int n_, T d) : n(n_), bit(n_ + 1, d) {}// initialization2 n_要素数 d初期値T sum(int i) {T s = bit[0];for(int x = i + 1; x > 0; x -= (x & -x)) s += bit[x];return s;}// 1からiまでの和(1-indexed)void add(int i, T a) {for(int x = i + 1; x <= n; x += (x & -x)) bit[x] += a;}// iにa加えるT lower_bound(T w) {if(w <= 0) return 0;T x = 0, r = 1; // xは横の位置を管理するイメージwhile(r < n) r <<= 1;for(T k = r; k > 0; k >>= 1) { //上の層から見るif(x + k <= n && bit[x + k] < w) {w -= bit[x + k];x += k; //右の要素に移る}}return x + 1;}// indまでの区間和がw以上になるような最小のindを求めるT query(int l, int r) { return sum(r - 1) - sum(l - 1); } // [l,r)の和(0-indexed)};template<typename T>struct compression{V<T> tmp;map<T,T> ma;void push(T x){tmp.emplace_back(x);}void build(){sort(all(tmp));tmp.erase(unique(all(tmp)),tmp.end());rep(i,0,siz(tmp))ma[tmp[i]]=i;//}void change(T& x){assert(ma.count(x));x=ma[x];}void change(V<T>& v){rep(i,0,siz(v)){assert(ma.count(v[i]));v[i]=ma[v[i]];}}};signed main(){cin.tie(0);cerr.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);ll n;cin>>n;V<ll> v(n);cin>>v;V<ll> id=v;compression<ll> com;rep(i,0,n)com.push(v[i]);com.build();com.change(id);BIT<ll> bl(n+5,0),br(n+5,0),numl(n+5,0),numr(n+5,0);rep(i,0,n){br.add(id[i],v[i]);numr.add(id[i],1);}M ans=0;rep(j,0,n){br.add(id[j],-v[j]);numr.add(id[j],-1);M l=numl.query(id[j]+1,n),r=numr.query(0,id[j]);ans+=r*bl.query(id[j]+1,n)+l*br.query(0,id[j])+r*l*v[j];bl.add(id[j],v[j]);numl.add(id[j],1);}cout<<ans<<ENDL;}//! ( . _ . ) !//CHECK overflow,vector_size,what to output?//any other simpler approach?//list all conditions, try mathematical and graphic observation