結果
問題 | No.1300 Sum of Inversions |
ユーザー |
![]() |
提出日時 | 2020-11-27 22:14:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 454 ms / 2,000 ms |
コード長 | 3,130 bytes |
コンパイル時間 | 1,046 ms |
コンパイル使用メモリ | 99,564 KB |
実行使用メモリ | 20,332 KB |
最終ジャッジ日時 | 2024-07-26 13:11:26 |
合計ジャッジ時間 | 12,476 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <cstdio> #include <string> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <iterator> #include <cassert> #include <numeric> #include <functional> #include <time.h> #pragma warning(disable:4996) //#define ATCODER #ifdef ATCODER #include <atcoder/all> #endif typedef long long ll; typedef unsigned long long ull; #define LINF 9223300000000000000 #define LINF2 1223300000000000000 #define LINF3 1000000000000 #define INF 2140000000 //const long long MOD = 1000000007; const long long MOD = 998244353; using namespace std; #ifdef ATCODER using namespace atcoder; #endif template<class T> class BIT // 1-indexed (0 is not used) { private: int num; vector<T> bit; public: BIT(int n) :bit(vector<T>(n + 1, make_pair(0,0))), num(n) {} T sum(int i) { // sum of 1..i if (!i) return make_pair(0,0); auto tmp0 = bit[i]; auto tmp1 = sum(i - (i&-i)); return make_pair((tmp0.first + tmp1.first)%MOD, (tmp0.second + tmp1.second) % MOD); } void add(int i, T x) { if (i > num) return; bit[i].first += x.first; bit[i].first %= MOD; bit[i].second += x.second; bit[i].second %= MOD; add(i + (i&-i), x); } int lower_bound(T x) { T res = 0; int N = 1; while (N < num) N *= 2; int i; for (i = N / 2; i > 0; i /= 2) { if (res + i < num && bit[res + i] < x) { x = x - bit[res + i]; res = res + i; } } return res + 1; } }; void solve() { int n; scanf("%d", &n); vector<int> a(n); map<int, int> mp; int i; for (i = 0; i < n; i++) { scanf("%d", &a[i]); mp[a[i]] = 0; } auto it = mp.begin(); vector<int> vmp; int cnt = 0; for (; it != mp.end(); ++it) { cnt++; it->second = cnt; vmp.push_back(it->first); } ll ans = 0; int num = cnt; BIT<pair<ll,ll> > bit(num); BIT<pair<ll,ll> > bit2(num); for (i = 0; i < n; i++) { auto tmp0=bit.sum(num); auto tmp1=bit.sum(mp[a[i]]); auto tmp2 = make_pair((tmp0.first - tmp1.first+MOD)%MOD, (tmp0.second - tmp1.second+MOD)%MOD); ll val = (tmp2.second + a[i] * tmp2.first %MOD) % MOD; //printf("%lld\n", val); auto tmp20 = bit2.sum(num); auto tmp21 = bit2.sum(mp[a[i]]); auto tmp22 = make_pair((tmp20.first - tmp21.first+MOD)%MOD, (tmp20.second - tmp21.second + MOD) % MOD); ll val2 = (tmp22.second + a[i] * tmp22.first %MOD) % MOD; ans = (ans + val2) % MOD; //printf("%lld\n", val); bit2.add(mp[a[i]], make_pair(tmp2.first, val)); bit.add(mp[a[i]], make_pair(1,(ll)a[i])); } printf("%lld\n", ans); return; } int main() { #if 1 solve(); #else int T; scanf("%d", &T); int t; for (t = 0; t < T; t++) { //printf("Case #%d: ", t + 1); solve(); } #endif return 0; }