結果
問題 | No.1300 Sum of Inversions |
ユーザー | hedwig100 |
提出日時 | 2020-11-27 22:15:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,507 bytes |
コンパイル時間 | 2,193 ms |
コンパイル使用メモリ | 188,188 KB |
実行使用メモリ | 39,176 KB |
最終ジャッジ日時 | 2023-10-01 06:24:30 |
合計ジャッジ時間 | 13,298 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 313 ms
30,876 KB |
testcase_04 | AC | 308 ms
30,088 KB |
testcase_05 | AC | 237 ms
25,340 KB |
testcase_06 | AC | 368 ms
34,064 KB |
testcase_07 | AC | 342 ms
32,708 KB |
testcase_08 | AC | 388 ms
35,600 KB |
testcase_09 | AC | 389 ms
35,616 KB |
testcase_10 | AC | 194 ms
21,668 KB |
testcase_11 | AC | 193 ms
22,044 KB |
testcase_12 | AC | 308 ms
30,028 KB |
testcase_13 | AC | 304 ms
29,632 KB |
testcase_14 | AC | 438 ms
38,412 KB |
testcase_15 | AC | 417 ms
35,240 KB |
testcase_16 | AC | 334 ms
31,252 KB |
testcase_17 | AC | 184 ms
21,044 KB |
testcase_18 | AC | 212 ms
23,644 KB |
testcase_19 | AC | 256 ms
26,992 KB |
testcase_20 | AC | 277 ms
27,788 KB |
testcase_21 | AC | 272 ms
27,584 KB |
testcase_22 | AC | 236 ms
25,196 KB |
testcase_23 | AC | 369 ms
33,908 KB |
testcase_24 | AC | 258 ms
26,080 KB |
testcase_25 | AC | 216 ms
23,060 KB |
testcase_26 | AC | 200 ms
22,744 KB |
testcase_27 | AC | 243 ms
24,744 KB |
testcase_28 | AC | 405 ms
36,512 KB |
testcase_29 | AC | 267 ms
27,612 KB |
testcase_30 | AC | 388 ms
35,688 KB |
testcase_31 | AC | 240 ms
25,688 KB |
testcase_32 | AC | 259 ms
26,312 KB |
testcase_33 | AC | 52 ms
16,684 KB |
testcase_34 | AC | 65 ms
16,608 KB |
testcase_35 | AC | 176 ms
38,956 KB |
testcase_36 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL_ void debug_out() {cerr << endl;} template<typename Head,typename... Tail> void debug_out(Head H,Tail... T){cerr << ' ' << H; debug_out(T...);} #define debug(...) cerr << 'L' << __LINE__ << " [" << #__VA_ARGS__ << "]:",debug_out(__VA_ARGS__) #define dump(x) cerr << 'L' << __LINE__ << " " << #x << " = " << (x) << endl; #else #define debug(...) (void(0)) #define dump(x) (void(0)) #endif #define rep(i,n) for (int i = 0; i < (int)(n); i ++) #define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i) using ll = long long; using PL = pair<ll,ll>; using P = pair<int,int>; constexpr int INF = 1000000000; constexpr long long HINF = 100000'00000'00000; constexpr long long MOD = 1000000007;// = 998244353; constexpr double EPS = 1e-4; constexpr double PI = 3.14159265358979; #pragma region Macros template<typename T1,typename T2> ostream &operator<<(ostream &os,const pair<T1,T2> &p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template<typename T> ostream &operator<<(ostream &os,const vector<T> &v) { os << '['; for (auto &e:v) {os << e << ',';} os << ']'; return os; } // grid searh const int dy[8] = {-1,0,1,0,-1,-1,1,1}; const int dx[8] = {0,1,0,-1,-1,1,-1,1}; bool IN(int y,int x,int H,int W) {return (0 <= y)&&(y < H)&&(0 <= x)&&(x < W);} #pragma endregion template<class T> struct BinaryIndexedTree { int N,power = 1; vector<T> bit; BinaryIndexedTree(int N = 0): N(N){ bit.assign(N + 1,0); while (power <= N) power <<= 1; //power > N } void build(const vector<T> &A) { for (int i = 1;i <= N; ++i) add(i,A[i - 1]); } // add x to a[i] void add(int i,T x) { for (int idx = i; idx <= N; idx += (idx & -idx)) { bit[idx] += x; } } // return a[1] + a[2] + a[3] + .. + a[k] T sum(int k) { T ret = 0; for (int idx = k; idx > 0; idx -= (idx & -idx)) { ret += bit[idx]; } return ret; } // return a[l] + a[l + 1] + a[l + 2] + .. + a[r - 1] T sum(int l,int r) { return sum(r - 1) - sum(l - 1); } // return min index s.t. a[1] + a[2] + a[3] + .. + a[x] >= w int lower_bound(T w) { if (w <= 0) return 0; int x = 0; for (int r = power; r > 0; r >>= 1) { if (x + r <= N && bit[x + r] < w) { w -= bit[x + r]; x += r; } } return x + 1; } }; template<int Modulus> struct ModInt { long long x; ModInt(long long x = 0) :x((x%Modulus + Modulus)%Modulus) {} constexpr ModInt &operator+=(const ModInt a) {if ((x += a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator-=(const ModInt a) {if ((x += Modulus - a.x) >= Modulus) x -= Modulus; return *this;} constexpr ModInt &operator*=(const ModInt a) {(x *= a.x) %= Modulus; return *this;} constexpr ModInt &operator/=(const ModInt a) {return *this *= a.inverse();} constexpr ModInt operator+(const ModInt a) const {return ModInt(*this) += a.x;} constexpr ModInt operator-(const ModInt a) const {return ModInt(*this) -= a.x;} constexpr ModInt operator*(const ModInt a) const {return ModInt(*this) *= a.x;} constexpr ModInt operator/(const ModInt a) const {return ModInt(*this) /= a.x;} friend constexpr ostream& operator<<(ostream& os,const ModInt<Modulus>& a) {return os << a.x;} friend constexpr istream& operator>>(istream& is,ModInt<Modulus>& a) {return is >> a.x;} ModInt inverse() const {// x ^ (-1) long long a = x,b = Modulus,p = 1,q = 0; while (b) {long long d = a/b; a -= d*b; swap(a,b); p -= d*q; swap(p,q);} return ModInt(p); } ModInt pow(long long N) {// x ^ N ModInt a = 1; while (N) { if (N&1) a *= *this; *this *= *this; N >>= 1; } return a; } }; using mint = ModInt<998244353>; map<ll,int> compress(vector<ll> A) { sort(A.begin(),A.end()); A.erase(unique(A.begin(),A.end()),A.end()); map<ll,int> mp; rep(i,A.size()) mp[A[i]] = i; return mp; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int N; cin >> N; vector<ll> A(N); rep(i,N) cin >> A[i]; auto mp = compress(A); int M = mp.size(); vector<vector<int>> B(M); rep(i,N) { int idx = mp[A[i]]; B[idx].push_back(i); } vector<ll> cntL(N),cntR(N); vector<mint> left(N),right(N); mint tot = 0; int bf = 0; BinaryIndexedTree<mint> bit(N); BinaryIndexedTree<int> idx(N); rep(i,M) { for (int j:B[i]) { left[j] = tot - bit.sum(j+1); cntL[j] = bf - idx.sum(j+1); } for (int j:B[i]) { bit.add(j+1,A[j]); idx.add(j+1,1); tot += A[j]; ++bf; } } BinaryIndexedTree<mint> bit2(N); BinaryIndexedTree<int> idx2(N); irep(i,M) { for (int j:B[i]) { right[j] = bit2.sum(j+1); cntR[j] = idx2.sum(j+1); } for (int j:B[i]) { bit2.add(j+1,A[j]); idx2.add(j+1,1); } } mint ans = 0; rep(i,N) { ans += cntL[i]*cntR[i]*A[i]; if (cntL[i] > 0 && cntR[i] > 0) { ans += right[i]*cntL[i]; ans += left[i]*cntR[i]; } } cout << ans << '\n'; return 0; }