結果

問題 No.1733 Sum of Sorted Subarrays
ユーザー 👑 PCTprobabilityPCTprobability
提出日時 2021-11-05 21:44:25
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,135 bytes
コンパイル時間 2,723 ms
コンパイル使用メモリ 219,484 KB
最終ジャッジ日時 2024-04-24 05:31:33
合計ジャッジ時間 4,099 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:117:53: error: unable to deduce 'auto' from 'op'
  117 |   lazy_segtree<S, op, e, F, mapping, composition, id> seg(u);
      |                                                     ^
main.cpp:117:53: note:   couldn't deduce template parameter 'auto'
main.cpp:117:53: error: unable to deduce 'auto' from 'mapping'
main.cpp:117:53: note:   couldn't deduce template parameter 'auto'
main.cpp:117:53: error: unable to deduce 'auto' from 'composition'
main.cpp:117:53: note:   couldn't deduce template parameter 'auto'
main.cpp:117:59: error: cannot convert 'std::vector<S>' to 'int' in initialization
  117 |   lazy_segtree<S, op, e, F, mapping, composition, id> seg(u);
      |                                                           ^
      |                                                           |
      |                                                           std::vector<S>
main.cpp:125:21: error: request for member 'prod' in 'seg', which is of non-class type 'int'
  125 |     r[b[i].se]+=seg.prod(b[i].se+1,n).value;
      |                     ^~~~
main.cpp:126:9: error: request for member 'apply' in 'seg', which is of non-class type 'int'
  126 |     seg.apply(b[i].se,n,1);
      |         ^~~~~
main.cpp:128:53: error: unable to deduce 'auto' from 'op'
  128 |   lazy_segtree<S, op, e, F, mapping, composition, id> seg2(u);
      |                                                     ^
main.cpp:128:53: note:   couldn't deduce template parameter 'auto'
main.cpp:128:53: error: unable to deduce 'auto' from 'mapping'
main.cpp:128:53: note:   couldn't deduce template parameter 'auto'
main.cpp:128:53: error: unable to deduce 'auto' from 'composition'
main.cpp:128:53: note:   couldn't deduce template parameter 'auto'
main.cpp:128:60: error: cannot convert 'std::vector<S>' to 'int' in initialization
  128 |   lazy_segtree<S, op, e, F, mapping, composition, id> seg2(u);
      |

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using ll = int;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int, int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define PB push_back
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define se second
#define pb push_back
#define P pair<ll,ll>
#define PQminll priority_queue<ll, vector<ll>, greater<ll>>
#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>
#define PQminP priority_queue<P, vector<P>, greater<P>>
#define PQmaxP priority_queue<P,vector<P>,less<P>>
#define NP next_permutation
typedef string::const_iterator State;
class ParseError {};
//const ll mod = 1000000009;
const ll mod = 998244353;
//const ll mod = 1000000007;
const ll inf = 1000000000;
const ld eps = ld(0.00000000000001);
//static const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
template<class T>void print(T a){cout<<a<<endl;}
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
P hyou(P a){ll x=fastgcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}
P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}
P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}
P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}
P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}
P Pgyaku(P a){ return hyou({a.se,a.fi});}

void cincout(){
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(15);
}
using mint = modint998244353;
//using mint = modint1000000007;
ostream &operator<<(ostream &os,mint m){
  os<<m.val();
  return os;
}
istream &operator>>(istream &is,mint m){
  ll x;
  is>>x;
  m=x;
  return is;
}
using mint = modint998244353;
struct S{
  mint value;
  int size;
};
using F = ll;
S op(S a,S b){return {a.value+b.value,a.size+b.size};}
S e(){return {0,0};}
S mapping(F f,S x){ return {x.value*mint(2).pow(f),x.size};}
F composition(F f, F g){ return f+g;}
F id(){ return 0;}
struct S2{
    long long value;
    int size;
};
using F2 = long long;

S2 op(S2 a, S2 b){ return {a.value+b.value, a.size+b.size}; }
S2 e2(){ return {0, 0}; }
S2 mapping(F2 f, S2 x){ return {x.value + f*x.size, x.size}; }
F2 composition(F2 f, F2 g){ return f+g; }
F2 id2(){ return 0; }
int main() {
  cincout();
  ll n;
  cin>>n;
  vector<S> u(n,{1,1});
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(u);
  vector<ll> a(n);
  vcin(a);
  vector<mint> l(n),r(n);
  vector<P> b;
  for(int i=0;i<n;i++) b.pb({a[i],i});
  sor(b);
  for(int i=0;i<n;i++){
    r[b[i].se]+=seg.prod(b[i].se+1,n).value;
    seg.apply(b[i].se,n,1);
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> seg2(u);
  for(int i=0;i<n;i++){
    l[b[i].se]+=seg2.prod(0,b[i].se).value;
    seg2.apply(0,b[i].se+1,1);
  }
/*  for(auto e:r) cout<<e<<" ";
  cout<<endl;
  for(auto e:l) cout<<e<<" ";
  cout<<endl;*/
  vector<S2> k(n,{0,1});
  lazy_segtree<S2, op, e2, F2, mapping, composition, id2> seg3(k);
  lazy_segtree<S2, op, e2, F2, mapping, composition, id2> seg4(k);
  for(int i=0;i<n;i++){
    r[b[i].se]/=mint(2).pow(seg3.prod(b[i].se,b[i].se+1).value);
    seg3.apply(b[i].se,n,1);
  }
  for(int i=0;i<n;i++){
    l[b[i].se]/=mint(2).pow(seg4.prod(b[i].se,b[i].se+1).value);
    seg4.apply(0,b[i].se,1);
  }
 // for(auto e:r) cout<<e<<" ";
 // cout<<endl;
 // for(auto e:l) cout<<e<<" ";
 // cout<<endl;
  for(auto &e:r) e++;
  for(auto &e:l) e++;
  mint ans=0;
  for(int i=0;i<n;i++) ans+=l[i]*r[i]*a[i];
  cout<<ans<<endl;
}
0