結果

問題 No.1300 Sum of Inversions
ユーザー 👑 NachiaNachia
提出日時 2020-11-27 22:20:49
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 2,024 bytes
コンパイル時間 2,998 ms
コンパイル使用メモリ 209,872 KB
実行使用メモリ 23,244 KB
最終ジャッジ日時 2023-10-01 06:33:47
合計ジャッジ時間 11,333 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 201 ms
22,484 KB
testcase_04 AC 193 ms
22,516 KB
testcase_05 AC 160 ms
13,956 KB
testcase_06 AC 236 ms
22,584 KB
testcase_07 AC 225 ms
22,940 KB
testcase_08 AC 244 ms
22,912 KB
testcase_09 AC 245 ms
22,980 KB
testcase_10 AC 127 ms
13,144 KB
testcase_11 AC 128 ms
13,148 KB
testcase_12 AC 194 ms
22,368 KB
testcase_13 AC 188 ms
22,112 KB
testcase_14 AC 268 ms
23,164 KB
testcase_15 AC 243 ms
22,892 KB
testcase_16 AC 206 ms
22,632 KB
testcase_17 AC 123 ms
13,272 KB
testcase_18 AC 141 ms
13,540 KB
testcase_19 AC 172 ms
22,184 KB
testcase_20 AC 179 ms
22,240 KB
testcase_21 AC 180 ms
22,184 KB
testcase_22 AC 161 ms
13,616 KB
testcase_23 AC 222 ms
22,772 KB
testcase_24 AC 157 ms
13,660 KB
testcase_25 AC 140 ms
13,400 KB
testcase_26 AC 135 ms
13,544 KB
testcase_27 AC 148 ms
13,780 KB
testcase_28 AC 245 ms
23,048 KB
testcase_29 AC 172 ms
22,108 KB
testcase_30 AC 238 ms
22,904 KB
testcase_31 AC 158 ms
13,812 KB
testcase_32 AC 160 ms
13,668 KB
testcase_33 AC 89 ms
23,244 KB
testcase_34 AC 140 ms
23,108 KB
testcase_35 AC 148 ms
23,124 KB
testcase_36 AC 165 ms
23,112 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: 関数 ‘int main()’ 内:
main.cpp:99:44: 警告: 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: 警告: 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: 警告: 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;
}
0