結果

問題 No.1300 Sum of Inversions
ユーザー 👑 Nachia
提出日時 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});
      |                          ^

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0