結果
問題 | No.1975 Zigzag Sequence |
ユーザー | kaichou243 |
提出日時 | 2022-06-11 20:28:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 4,112 bytes |
コンパイル時間 | 2,404 ms |
コンパイル使用メモリ | 215,656 KB |
実行使用メモリ | 8,804 KB |
最終ジャッジ日時 | 2024-09-22 07:01:21 |
合計ジャッジ時間 | 6,415 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 15 ms
6,940 KB |
testcase_04 | AC | 7 ms
6,944 KB |
testcase_05 | AC | 125 ms
8,580 KB |
testcase_06 | AC | 81 ms
6,940 KB |
testcase_07 | AC | 16 ms
6,944 KB |
testcase_08 | AC | 81 ms
6,940 KB |
testcase_09 | AC | 118 ms
8,596 KB |
testcase_10 | AC | 84 ms
6,940 KB |
testcase_11 | AC | 94 ms
8,300 KB |
testcase_12 | AC | 23 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,944 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 1 ms
6,944 KB |
testcase_17 | AC | 1 ms
6,940 KB |
testcase_18 | AC | 91 ms
8,672 KB |
testcase_19 | AC | 92 ms
8,676 KB |
testcase_20 | AC | 100 ms
8,800 KB |
testcase_21 | AC | 99 ms
8,668 KB |
testcase_22 | AC | 120 ms
8,676 KB |
testcase_23 | AC | 119 ms
8,800 KB |
testcase_24 | AC | 124 ms
8,796 KB |
testcase_25 | AC | 125 ms
8,672 KB |
testcase_26 | AC | 131 ms
8,592 KB |
testcase_27 | AC | 144 ms
8,740 KB |
testcase_28 | AC | 123 ms
8,804 KB |
testcase_29 | AC | 123 ms
8,768 KB |
testcase_30 | AC | 123 ms
8,672 KB |
testcase_31 | AC | 122 ms
8,668 KB |
testcase_32 | AC | 92 ms
8,672 KB |
testcase_33 | AC | 93 ms
8,672 KB |
testcase_34 | AC | 127 ms
8,676 KB |
testcase_35 | AC | 128 ms
8,740 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll=long long; template<int MOD> struct Fp{ ll val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } static constexpr int getmod() { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { ll a = r.val, b = MOD, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } constexpr bool operator < (const Fp& r) const noexcept { return this->val < r.val; } friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept { return os << x.val; } friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept { Fp<MOD> res=1,r=a; while(n){ if(n&1) res*=r; r*=r; n>>=1; } return res; } friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } return Fp<MOD>(u); } explicit operator bool()const{ return val; } }; template<class T,T (*op)(T,T),T (*e)()> struct SegmentTree{ int n; vector<T> dat; SegmentTree(int N){ n=1; while(n<N)n*=2; dat.assign(2*n,e()); } void add(int k,T x){ k+=n; dat[k]+=x; while(k){ k>>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } void apply(int k,T x){ k+=n; dat[k]=op(dat[k],x); while(k){ k>>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } void set(int k,T x){ k+=n; dat[k]=x; while(k){ k>>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } T query(int l,int r){ T prodl=e(),prodr=e(); l+=n; r+=n; while(l<r){ if(l&1) prodl=op(prodl,dat[l++]); if(r&1) prodr=op(dat[--r],prodr); l>>=1; r>>=1; } return op(prodl,prodr); } }; template <typename T> vector<int> compress(vector<T> &x){ vector<T> vals=x; vector<int> res; sort(vals.begin(),vals.end()); auto it=unique(vals.begin(),vals.end()); vals.erase(it,vals.end()); for(auto xx : x){ int ret=lower_bound(vals.begin(),vals.end(),xx) - vals.begin(); res.push_back(ret); } return res; } using mint=Fp<1000000007>; mint op(mint a,mint b){ return a+b; } mint e(){ return mint(0); } int main(){ int n; cin>>n; vector<ll> a(n); for(int i=0;i<n;i++) cin>>a[i]; vector<int> A=compress(a); SegmentTree<mint,op,e> stl(n),str(n); for(int i=1;i<n;i++){ str.add(A[i],modpow(mint(2),n-1-i)); } mint ans=0; stl.add(A[0],modpow(mint(2),0)); for(int i=1;i<n-1;i++){ str.add(A[i],-modpow(mint(2),n-1-i)); ans+=stl.query(0,A[i])*str.query(0,A[i]); ans+=stl.query(A[i]+1,n)*str.query(A[i]+1,n); stl.add(A[i],modpow(mint(2),i)); } cout<<ans<<endl; }