結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 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-indexed BIT() : 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