結果
問題 | No.1300 Sum of Inversions |
ユーザー | T1610 |
提出日時 | 2020-11-30 15:25:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,801 ms / 2,000 ms |
コード長 | 6,571 bytes |
コンパイル時間 | 2,821 ms |
コンパイル使用メモリ | 227,384 KB |
実行使用メモリ | 120,520 KB |
最終ジャッジ日時 | 2024-09-13 02:24:06 |
合計ジャッジ時間 | 43,016 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,812 KB |
testcase_03 | AC | 1,299 ms
93,640 KB |
testcase_04 | AC | 1,221 ms
91,048 KB |
testcase_05 | AC | 981 ms
76,172 KB |
testcase_06 | AC | 1,454 ms
104,428 KB |
testcase_07 | AC | 1,421 ms
100,008 KB |
testcase_08 | AC | 1,640 ms
110,056 KB |
testcase_09 | AC | 1,591 ms
109,264 KB |
testcase_10 | AC | 791 ms
63,828 KB |
testcase_11 | AC | 840 ms
64,516 KB |
testcase_12 | AC | 1,294 ms
91,588 KB |
testcase_13 | AC | 1,248 ms
89,520 KB |
testcase_14 | AC | 1,801 ms
118,780 KB |
testcase_15 | AC | 1,555 ms
108,560 KB |
testcase_16 | AC | 1,375 ms
95,824 KB |
testcase_17 | AC | 746 ms
62,064 KB |
testcase_18 | AC | 885 ms
70,340 KB |
testcase_19 | AC | 1,128 ms
81,804 KB |
testcase_20 | AC | 1,190 ms
83,400 KB |
testcase_21 | AC | 1,210 ms
83,316 KB |
testcase_22 | AC | 1,047 ms
76,140 KB |
testcase_23 | AC | 1,629 ms
104,096 KB |
testcase_24 | AC | 1,082 ms
78,392 KB |
testcase_25 | AC | 873 ms
68,224 KB |
testcase_26 | AC | 854 ms
67,032 KB |
testcase_27 | AC | 959 ms
74,100 KB |
testcase_28 | AC | 1,706 ms
112,328 KB |
testcase_29 | AC | 1,066 ms
82,648 KB |
testcase_30 | AC | 1,645 ms
109,072 KB |
testcase_31 | AC | 1,008 ms
76,828 KB |
testcase_32 | AC | 1,056 ms
79,232 KB |
testcase_33 | AC | 138 ms
6,940 KB |
testcase_34 | AC | 194 ms
6,940 KB |
testcase_35 | AC | 730 ms
120,264 KB |
testcase_36 | AC | 754 ms
120,520 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; const ll INF = 1e18; const ll MOD = 1e9 + 7; template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);} template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);} #define DEBUG_MODE #ifdef DEBUG_MODE #define dump(x) cout << #x << " : " << x << " " #define dumpL(x) cout << #x << " : " << x << '\n' #define LINE cout << "line : " << __LINE__ << " " #define LINEL cout << "line : " << __LINE__ << '\n' #define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " " #define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl #define STOP assert(false) #else #define dump(x) #define dumpL(x) #define LINE #define LINEL #define dumpV(v) #define dumpVL(v) #define STOP assert(false) #endif #define mp make_pair namespace std { template<class S, class T> ostream &operator <<(ostream& out, const pair<S, T>& a) { out << '(' << a.fi << ", " << a.se << ')'; return out; } } template<typename T> tuple<map<T, int>, vector<T>> zaatu(const vector<vector<T>>& v) { map<T, int> mp; for(auto&& u: v) for(auto&& x: u) mp[x] = 0; vector<T> r; for(auto& p: mp) { p.second = r.size(); r.emplace_back(p.first); } return {mp, r}; } template <typename T, typename U> T pow_fast(T x, U n) { T ret = (T)1; while(n) { if(n & (U)1) ret *= x; x *= x; n >>= 1; } return ret; } template <typename ModType, ModType MOD> struct ModInt { ModType val; ModInt() : val(0) {} ModInt(ModType x) : val(x % MOD) { if(val < 0) val += MOD; }; operator ModType() const { return val; } ModInt &operator+=(const ModInt &m) { val += m.val; if(val >= MOD) val -= MOD; return *this; } ModInt &operator-=(const ModInt &m) { val -= m.val; if(val < 0) val += MOD; return *this; } ModInt &operator*=(const ModInt &m) { (val *= m.val) %= MOD; return *this; } ModInt &operator/=(const ModInt &m) { *this *= m.inverse(); return *this; } ModInt operator+(const ModInt &m) const { return ModInt(*this) += m; } ModInt operator-(const ModInt &m) const { return ModInt(*this) -= m; } ModInt operator*(const ModInt &m) const { return ModInt(*this) *= m; } ModInt operator/(const ModInt &m) const { return ModInt(*this) /= m; } ModInt inverse() const { return pow_fast(*this, MOD - 2); } ModInt pow(ModType n) const {return pow_fast(*this, n); } friend std::ostream &operator<<(std::ostream &os, const ModInt &rhs) { os << rhs.val; return os; } friend std::istream &operator>>(std::istream &is, ModInt &rhs) { ModType value; is >> value; rhs = ModInt(value); return is; } }; using mint = ModInt<ll, 998244353LL>; using ull = unsigned long long; template <typename T> struct Node { static inline const T initVal = 0; //TODO: fix type and value static inline const T initLazy = 0; //TODO: fix type and value T val; T lazy; ull l, r; Node<T>* l_node = nullptr; Node<T>* r_node = nullptr; Node(ull l, ull r, const T& val = initVal) : l(l), r(r), val(val), lazy(initLazy) {} T getVal() { return val + lazy * T(r - l); //TODO: fix } T f1(const T& a, const T& b) { return a+b; //TODO: fix } T f2(const T& a, const T& b) { return a+b; //TODO: fix } void push() { if(r - l > 1) { auto m = (l+r)/2; { if(l_node == nullptr) l_node = new Node(l, m); if(lazy != initLazy) l_node->lazy = f2(l_node->lazy, this->lazy); } { if(r_node == nullptr) r_node = new Node(m, r); if(lazy != initLazy) r_node->lazy = f2(r_node->lazy, this->lazy); } } val = getVal(); lazy = initLazy; } void fix() { if(r - l == 1) return; val = f1(l_node->getVal(), r_node->getVal()); } T query(ull qL, ull qR) { if(qR <= l || r <= qL) return initVal; if(qL <= l && r <= qR) return getVal(); if(r - l == 1) return getVal(); push(); T l_val = l_node->query(qL, qR), r_val = r_node->query(qL, qR); return f1(l_val, r_val); } void update(ull uL, ull uR, const T& uVal) { if(uR <= l || r <= uL) return; if(uL <= l && r <= uR) lazy = f2(lazy, uVal); else { push(); l_node->update(uL, uR, uVal); r_node->update(uL, uR, uVal); fix(); } } }; template <typename T> struct DynamicLazySegTree { Node<T> root; DynamicLazySegTree(ull l, ull r, const T& val) : root(l, r, val) {} DynamicLazySegTree(ull r): root(0, r) {} T query(ull l, ull r) { return root.query(l, r); } void update(ull l, ull r, const T& val) { root.update(l, r, val); } void output() { auto l = root.l; auto r = root.r; REP(i, l, r) { cout << " " << query(i, i+1); } cout << '\n'; } }; int main(){ int n; cin >> n; vl a(n); rep(i, n) cin >> a[i]; vector<vl> aa(1, a); auto [mp, v] = zaatu(aa); DynamicLazySegTree<mint> seg1(n+10), seg2(n+10); DynamicLazySegTree<ll> cnt1(n+10), cnt2(n+10); mint ans = 0; repr(i, n) { int cur = mp[a[i]]; // dump(i);dump(cur);dumpL(a[i]); seg1.update(cur, cur+1, a[i]); cnt1.update(cur, cur+1, 1); if(cur > 0) { seg2.update(cur, cur+1, seg1.query(0, cur)+mint(cnt1.query(0, cur))*mint(a[i])); cnt2.update(cur, cur+1, cnt1.query(0, cur)); } if(cur > 0) { // auto tmp = seg2.query(0, cur) + mint(cnt2.query(0, cur) * a[i]); // dumpL(tmp); ans += seg2.query(0, cur) + mint(cnt2.query(0, cur)) * mint(a[i]); } // seg1.output(); // cnt1.output(); // seg2.output(); // cnt2.output(); } cout << ans << '\n'; return 0; }