結果
問題 | No.1300 Sum of Inversions |
ユーザー |
👑 ![]() |
提出日時 | 2020-11-27 22:20:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 274 ms / 2,000 ms |
コード長 | 2,024 bytes |
コンパイル時間 | 2,416 ms |
コンパイル使用メモリ | 205,188 KB |
最終ジャッジ日時 | 2025-01-16 07:43:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:99:44: warning: narrowing conversion of ‘A.std::vector<int>::operator[](((std::vector<int>::size_type)i))’ from ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} to ‘ULL’ {aka ‘long long unsigned int’} [-Wnarrowing] 99 | ans = ans + G2.prod(0,lb[i]) * S{A[i],1}; | ^ main.cpp:100:56: warning: narrowing conversion of ‘A.std::vector<int>::operator[](((std::vector<int>::size_type)i))’ from ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} to ‘ULL’ {aka ‘long long unsigned int’} [-Wnarrowing] 100 | G2.set(I[i], G2.get(I[i])+G1.prod(0,lb[i])*S{A[i],1}); | ^ main.cpp:101:26: warning: narrowing conversion of ‘A.std::vector<int>::operator[](((std::vector<int>::size_type)i))’ from ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’} to ‘ULL’ {aka ‘long long unsigned int’} [-Wnarrowing] 101 | G1.set(I[i], S{A[i],1}); | ^
ソースコード
#include<bits/stdc++.h>using namespace std;using LL=long long;using ULL=unsigned long long;#define rep(i,n) for(int i=0;i<(n);i++)const ULL M = 998244353;template<class S,S(*op)(S a, S b),S(*e)()>struct segtree {private:int N;vector<S> V;public:segtree(int n) {N = 1; while (N < n) N *= 2;V.assign(N * 2, e());}segtree(vector<S> A) {N = 1; while (N < A.size()) N *= 2;V.assign(N * 2, e());rep(i, A.size()) V[N + i] = A[i];for (int i = N - 1; i >= 1; i--)V[i] = op(V[i * 2], V[i * 2 + 1]);}void set(int p, S v) {p += N;V[p] = v;while (p != 1) {p /= 2;V[p] = op(V[p * 2], V[p * 2 + 1]);}}S get(int p) {p += N;return V[p];}S prod(int l, int r) {S ans_l = e(), ans_r = e();l += N; r += N;while (l < r) {if (l & 1) ans_l = op(ans_l, V[l++]);if (r & 1) ans_r = op(V[--r], ans_r);l /= 2; r /= 2;}return op(ans_l, ans_r);}};struct S{ULL s,c;};S operator+(S l, S r){S res = { l.s+r.s, l.c+r.c };if(res.s>=M) res.s-=M;if(res.c>=M) res.c-=M;return res;}S operator*(S l, S r){return { (l.s*r.c+l.c*r.s)%M, l.c*r.c%M};}S op(S l, S r) { return l+r; }S e() { return {0,0}; }using RQ = segtree<S, op, e>;int lower_bound_idx(const vector<pair<int,int>>& ref, pair<int,int> v){int l,r; l=0; r=ref.size()+1;while(l+1<r){int m=(l+r)/2;if(ref[m-1]<v) l=m;else r=m;}return l;}int main(){int N; cin>>N;vector<int> A(N); rep(i,N) cin>>A[i];vector<pair<int,int>> xA(N); rep(i,N) xA[i]={-A[i],i};sort(xA.begin(),xA.end());vector<int> I(N); rep(i,N) I[xA[i].second]=i;vector<int> lb(N); rep(i,N) lb[i]=lower_bound_idx(xA,{-A[i],-1});rep(i,N) A[i]%=M;RQ G1(N);RQ G2(N);S ans=e();rep(i,N){ans = ans + G2.prod(0,lb[i]) * S{A[i],1};G2.set(I[i], G2.get(I[i])+G1.prod(0,lb[i])*S{A[i],1});G1.set(I[i], S{A[i],1});}cout<<ans.s<<endl;return 0;}