結果
問題 | No.1300 Sum of Inversions |
ユーザー | tarattata1 |
提出日時 | 2020-11-27 22:14:51 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 502 ms / 2,000 ms |
コード長 | 3,130 bytes |
コンパイル時間 | 1,315 ms |
コンパイル使用メモリ | 97,508 KB |
実行使用メモリ | 19,912 KB |
最終ジャッジ日時 | 2023-10-01 06:23:06 |
合計ジャッジ時間 | 13,944 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 384 ms
15,944 KB |
testcase_04 | AC | 341 ms
15,780 KB |
testcase_05 | AC | 279 ms
13,396 KB |
testcase_06 | AC | 427 ms
17,744 KB |
testcase_07 | AC | 405 ms
16,968 KB |
testcase_08 | AC | 469 ms
18,344 KB |
testcase_09 | AC | 461 ms
18,292 KB |
testcase_10 | AC | 215 ms
11,612 KB |
testcase_11 | AC | 223 ms
11,588 KB |
testcase_12 | AC | 366 ms
15,696 KB |
testcase_13 | AC | 358 ms
15,424 KB |
testcase_14 | AC | 502 ms
19,628 KB |
testcase_15 | AC | 469 ms
18,300 KB |
testcase_16 | AC | 382 ms
16,460 KB |
testcase_17 | AC | 208 ms
11,452 KB |
testcase_18 | AC | 259 ms
12,704 KB |
testcase_19 | AC | 313 ms
14,128 KB |
testcase_20 | AC | 321 ms
14,628 KB |
testcase_21 | AC | 316 ms
14,596 KB |
testcase_22 | AC | 284 ms
13,456 KB |
testcase_23 | AC | 426 ms
17,664 KB |
testcase_24 | AC | 295 ms
13,924 KB |
testcase_25 | AC | 238 ms
12,272 KB |
testcase_26 | AC | 233 ms
12,148 KB |
testcase_27 | AC | 270 ms
13,292 KB |
testcase_28 | AC | 472 ms
18,892 KB |
testcase_29 | AC | 312 ms
14,460 KB |
testcase_30 | AC | 447 ms
18,296 KB |
testcase_31 | AC | 268 ms
13,504 KB |
testcase_32 | AC | 305 ms
13,992 KB |
testcase_33 | AC | 25 ms
4,376 KB |
testcase_34 | AC | 38 ms
4,380 KB |
testcase_35 | AC | 246 ms
19,780 KB |
testcase_36 | AC | 251 ms
19,912 KB |
ソースコード
#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; }