結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 21:52:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 767 bytes |
コンパイル時間 | 4,419 ms |
コンパイル使用メモリ | 256,340 KB |
最終ジャッジ日時 | 2025-01-29 19:48:17 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint1000000007; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ int n; cin>>n; vector<int> a(n); rep(i,n)cin>>a[i]; { auto t =a; sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); rep(i,n){ a[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),a[i])); } } fenwick_tree<mint> X(n),Y(n); rep(i,n){ Y.add(a[i],mint(2).pow(n-1-i)); } mint ans = 0; rep(i,n){ Y.add(a[i],-mint(2).pow(n-1-i)); ans += X.sum(0,a[i]) * Y.sum(0,a[i]); ans += X.sum(a[i]+1,n) * Y.sum(a[i]+1,n); X.add(a[i],mint(2).pow(i)); } cout<<ans.val()<<endl; return 0; }