結果
問題 | No.1300 Sum of Inversions |
ユーザー | sapphire__15 |
提出日時 | 2020-11-28 00:27:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 345 ms / 2,000 ms |
コード長 | 6,262 bytes |
コンパイル時間 | 1,341 ms |
コンパイル使用メモリ | 125,816 KB |
実行使用メモリ | 18,028 KB |
最終ジャッジ日時 | 2023-10-09 22:56:27 |
合計ジャッジ時間 | 10,812 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,352 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 261 ms
14,484 KB |
testcase_04 | AC | 254 ms
14,076 KB |
testcase_05 | AC | 194 ms
12,360 KB |
testcase_06 | AC | 305 ms
15,928 KB |
testcase_07 | AC | 297 ms
15,436 KB |
testcase_08 | AC | 331 ms
16,512 KB |
testcase_09 | AC | 317 ms
16,376 KB |
testcase_10 | AC | 159 ms
10,708 KB |
testcase_11 | AC | 159 ms
10,612 KB |
testcase_12 | AC | 259 ms
14,064 KB |
testcase_13 | AC | 245 ms
13,964 KB |
testcase_14 | AC | 345 ms
17,624 KB |
testcase_15 | AC | 309 ms
16,316 KB |
testcase_16 | AC | 269 ms
14,788 KB |
testcase_17 | AC | 149 ms
10,404 KB |
testcase_18 | AC | 179 ms
11,488 KB |
testcase_19 | AC | 223 ms
13,088 KB |
testcase_20 | AC | 235 ms
12,972 KB |
testcase_21 | AC | 222 ms
13,040 KB |
testcase_22 | AC | 192 ms
12,228 KB |
testcase_23 | AC | 288 ms
15,912 KB |
testcase_24 | AC | 196 ms
12,640 KB |
testcase_25 | AC | 167 ms
11,296 KB |
testcase_26 | AC | 164 ms
11,256 KB |
testcase_27 | AC | 193 ms
11,956 KB |
testcase_28 | AC | 323 ms
16,908 KB |
testcase_29 | AC | 228 ms
13,104 KB |
testcase_30 | AC | 309 ms
16,364 KB |
testcase_31 | AC | 186 ms
12,376 KB |
testcase_32 | AC | 197 ms
12,556 KB |
testcase_33 | AC | 95 ms
17,896 KB |
testcase_34 | AC | 148 ms
18,008 KB |
testcase_35 | AC | 196 ms
18,028 KB |
testcase_36 | AC | 217 ms
17,896 KB |
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <bitset> #include <climits> #include <cmath> #include <bitset> #include <complex> #include <functional> #include <cassert> #include <stack> typedef long long ll; typedef std::pair<int, int> Pii; typedef std::pair<long long, long long> Pll; typedef std::pair<double, double> Pdd; #define rip(i, n, ss) for (int i = (ss);i < (int)( n ); i++) #define all(l) l.begin(), l.end() #define MM << " " << template<typename T> using MaxHeap = std::priority_queue<T>; template<typename T> using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>; template<typename T> inline bool chmax(T &l, const T b) { if (l < b) { l = b; return true; } return false; } template<typename T> inline bool chmin(T &l, const T b) { if (l > b) { l = b; return true; } return false; } # ifdef LOCAL_DEBUG template<typename T> void vdeb(const std::vector<T> &bb) { for (unsigned int i = 0;i < bb.size();i++) { if (i == bb.size() - 1) std::cout << bb[i]; else std::cout << bb[i] << ' '; } std::cout << '\n'; } template<typename T> void vdeb(const std::vector<std::vector<T>> &bb) { for (unsigned int i = 0;i < bb.size();i++) { std::cout << i << ' '; vdeb(bb[i]); } std::cout << '\n'; } # endif long long pow(long long n, long long p, long long k) {//n^k(mod p) if (!k) return 1; long long a = pow(n,p, k>>1); a = a * a%p; if (k & 1) a = a * n%p; return a; } void euclid(long long &a, long long &b, long long p) { // a>=b A*b+B*(a-a/b*b)=1 if (a == 1) { a = 1; } else { long long A = b, B = a % b; euclid(A, B, p); b = (A - (p + a / b) % p * B % p + p) % p; a = B; } } long long rev(long long n, long long p) {// n*x-p*y=1 //long long q = p; //euclid(p, n, p); //return n % q; return pow(n,p,p-2); } long long bino(long long n, long long m, long long p) {//nCm(mod p) long long ans = 1, div = 1; for(int i = 0;i < m; i++){ ans = (n - i) * ans % p; div = div * (i +1) % p; } return ans * rev(div, p) % p; } struct modint { long long num; long long p; modint() { num = 0; p = 998244353; } modint(long long x) { p = 998244353; num = x % p; } modint inv()const{return rev(num, p);} modint operator-() const{return modint(p-num);} modint& operator+=(const modint &other){ num = (num + other.num) % p; return *this; } modint& operator-=(const modint &other){ num = (num - other.num + p) % p; return *this; } modint& operator*=(const modint &other){ num = (num * other.num) % p; return *this; } modint& operator/=(const modint &other){ (*this) *= other.inv(); return *this; } modint& operator+=(const long long &other){ num = (num + other) % p; return *this; } modint& operator-=(const long long &other){ num = (num - other + p) % p; return *this; } modint& operator*=(const long long &other){ num = (num * other) % p; return *this; } modint& operator/=(const long long &other){ (*this) *= rev(other, p); return *this; } modint& operator++(){return *this += 1;} modint& operator--(){return *this -= 1;} modint& operator=(const long long &other){return (*this) = modint(other);} modint operator+(const modint &other) const{return modint(*this) += other;} modint operator-(const modint &other) const{return modint(*this) -= other;} modint operator*(const modint &other) const{return modint(*this) *= other;} modint operator/(const modint &other) const{return modint(*this) /= other;} modint operator+(const long long &other) const{return modint(*this) += other;} modint operator-(const long long &other) const{return modint(*this) -= other;} modint operator*(const long long &other) const{return modint(*this) *= other;} modint operator/(const long long &other) const{return modint(*this) /= other;} bool operator==(const modint &other) const{return num == other.num;} }; std::istream& operator>>(std::istream &is, const modint x) { std::cin >> x.num; return is; } std::ostream& operator<<(std::ostream &os, const modint &x){ std::cout << x.num; return os; } template<typename T> struct BIT{ std::vector<T> li; int size; BIT (int n){ li=std::vector<T>(n+1); size=n; } T sum (int i){ // sum of [0, n) assert(0 <= i && i <= size); if(i == 0) return 0; T s=0; while(i>0){ s+=li[i]; i-=i & -i; } return s; } T sum(int i, int j) { // sum of [i, j) assert(i < j); return sum(j) - sum(i); } void add(int i,T x){ // li[i] += x assert(0 <= i && i < size); ++i; while(i<=size){ li[i]+=x; i+=i & -i; } } }; using namespace std; int main() { int n; cin >> n; vector<Pii> da(n); vector<int> st(n); rip(i,n,0) { cin >> da[i].first; da[i].second = i; } sort(all(da)); reverse(all(da)); rip(i,n,0) { st[da[i].second] = i; swap(da[i].first, da[i].second); } sort(all(da)); BIT<modint> one(n), two(n), onep(n), twop(n); modint ans; rip(i,n,0) { int now = st[i]; if(onep.sum(now) == 0) { one.add(now, modint(da[i].second)); onep.add(now, modint(1)); } else if(onep.sum(now) == 1) { two.add(now, one.sum(now) + onep.sum(now)*da[i].second); twop.add(now, onep.sum(now)); one.add(now, modint(da[i].second)); onep.add(now, modint(1)); } else { ans += two.sum(now) + twop.sum(now) * da[i].second; two.add(now, one.sum(now) +onep.sum(now)* da[i].second); twop.add(now, onep.sum(now)); one.add(now, modint(da[i].second)); onep.add(now, modint(1)); } } cout << ans << endl; }