結果
問題 | No.1300 Sum of Inversions |
ユーザー | 259_Momone |
提出日時 | 2020-11-27 22:16:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 2,718 bytes |
コンパイル時間 | 2,654 ms |
コンパイル使用メモリ | 205,952 KB |
最終ジャッジ日時 | 2025-01-16 07:39:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include<bits/stdc++.h>int main(){using namespace std;const auto N{[]{unsigned long N; cin >> N; return N;}()};auto perm{[&N]{vector<pair<unsigned long, unsigned long>> ret(N);unsigned long idx{0};for(auto&& [p, i] : ret){cin >> p;i = idx++;}return ret;}()};const auto small{[&N, &perm]{sort(begin(perm), end(perm));vector<complex<unsigned long>> segtree(N * 2);vector<pair<unsigned long, unsigned long>> ret(N);const auto update{[&N, &segtree](unsigned long idx, const auto& val){idx += N;segtree[idx] += val;while(idx >>= 1UL)segtree[idx] += val;}};const auto fold{[&N, &segtree](unsigned long l, unsigned long r){decltype(segtree)::value_type ret{};l += N;r += N;while(l < r){if(l & 1UL)ret += segtree[l++];if(r & 1UL)ret += segtree[--r];l >>= 1UL;r >>= 1UL;}return ret;}};for(const auto& [p, i] : perm){const auto& tmp{fold(i, N)};ret[i] = {tmp.real(), tmp.imag()};update(i, complex{p, 1UL});}return ret;}()};const auto large{[&N, &perm]{reverse(begin(perm), end(perm));vector<complex<unsigned long>> segtree(N * 2);vector<pair<unsigned long, unsigned long>> ret(N);const auto update{[&N, &segtree](unsigned long idx, const auto& val){idx += N;segtree[idx] += val;while(idx >>= 1UL)segtree[idx] += val;}};const auto fold{[&N, &segtree](unsigned long l, unsigned long r){decltype(segtree)::value_type ret{};l += N;r += N;while(l < r){if(l & 1UL)ret += segtree[l++];if(r & 1UL)ret += segtree[--r];l >>= 1UL;r >>= 1UL;}return ret;}};for(const auto& [p, i] : perm){const auto& tmp{fold(0, i)};ret[i] = {tmp.real(), tmp.imag()};update(i, complex{p, 1UL});}return ret;}()};unsigned long ans{0};sort(begin(perm), end(perm), [](const auto& i, const auto& j){return i.second < j.second;});constexpr unsigned long MOD{998244353};for(unsigned long i{0}; i < N; ++i)ans += small[i].second * large[i].second % MOD * perm[i].first % MOD + small[i].second * large[i].first % MOD +small[i].first * large[i].second % MOD;cout << ans % MOD << endl;return 0;}