結果
| 問題 | No.1300 Sum of Inversions |
| ユーザー |
 T1610
|
| 提出日時 | 2020-11-30 15:04:36 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,369 bytes |
| コンパイル時間 | 3,060 ms |
| コンパイル使用メモリ | 223,448 KB |
| 実行使用メモリ | 102,196 KB |
| 最終ジャッジ日時 | 2023-10-11 02:51:19 |
| 合計ジャッジ時間 | 37,572 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,352 KB |
| testcase_02 | AC | 1 ms
4,348 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | AC | 142 ms
4,628 KB |
| testcase_34 | AC | 193 ms
4,640 KB |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
ソースコード
#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);}
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, Node<T>::initVal) {}
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);
}
};
int main(){
int n;
cin >> n;
vi a(n);
rep(i, n) cin >> a[i];
vector<vi> aa(1, a);
auto [mp, v] = zaatu(aa);
DynamicLazySegTree<mint> seg1(n+10), seg2(n+10);
DynamicLazySegTree<int> cnt1(n+10), cnt2(n+10);
mint ans = 0;
repr(i, n) {
int cur = mp[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)*a[i]));
cnt2.update(cur, cur+1, cnt1.query(0, cur));
}
if(cur > 0) {
ans += seg2.query(0, cur) + mint(cnt2.query(0, cur) * a[i]);
}
}
cout << ans << '\n';
return 0;
}