結果
問題 | No.1300 Sum of Inversions |
ユーザー | Hyado |
提出日時 | 2020-11-27 22:01:41 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 5,364 bytes |
コンパイル時間 | 2,698 ms |
コンパイル使用メモリ | 182,724 KB |
実行使用メモリ | 26,532 KB |
最終ジャッジ日時 | 2023-10-01 05:53:24 |
合計ジャッジ時間 | 12,588 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 274 ms
21,204 KB |
testcase_04 | AC | 262 ms
20,588 KB |
testcase_05 | AC | 213 ms
17,572 KB |
testcase_06 | AC | 327 ms
23,424 KB |
testcase_07 | AC | 313 ms
22,576 KB |
testcase_08 | AC | 354 ms
24,288 KB |
testcase_09 | AC | 347 ms
24,248 KB |
testcase_10 | AC | 166 ms
15,152 KB |
testcase_11 | AC | 167 ms
15,168 KB |
testcase_12 | AC | 273 ms
20,624 KB |
testcase_13 | AC | 257 ms
20,360 KB |
testcase_14 | AC | 386 ms
26,080 KB |
testcase_15 | AC | 345 ms
23,964 KB |
testcase_16 | AC | 280 ms
21,532 KB |
testcase_17 | AC | 156 ms
15,008 KB |
testcase_18 | AC | 190 ms
16,436 KB |
testcase_19 | AC | 236 ms
18,764 KB |
testcase_20 | AC | 249 ms
19,164 KB |
testcase_21 | AC | 242 ms
19,156 KB |
testcase_22 | AC | 213 ms
17,684 KB |
testcase_23 | AC | 322 ms
23,068 KB |
testcase_24 | AC | 211 ms
18,068 KB |
testcase_25 | AC | 175 ms
16,204 KB |
testcase_26 | AC | 169 ms
15,740 KB |
testcase_27 | AC | 199 ms
17,360 KB |
testcase_28 | AC | 355 ms
25,020 KB |
testcase_29 | AC | 225 ms
18,944 KB |
testcase_30 | AC | 344 ms
24,308 KB |
testcase_31 | AC | 211 ms
17,612 KB |
testcase_32 | AC | 222 ms
18,328 KB |
testcase_33 | AC | 101 ms
13,984 KB |
testcase_34 | AC | 115 ms
14,004 KB |
testcase_35 | AC | 189 ms
26,404 KB |
testcase_36 | AC | 198 ms
26,532 KB |
ソースコード
//#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