結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:01:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 3,602 bytes |
コンパイル時間 | 3,207 ms |
コンパイル使用メモリ | 261,916 KB |
実行使用メモリ | 12,728 KB |
最終ジャッジ日時 | 2024-09-21 06:46:29 |
合計ジャッジ時間 | 8,081 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < (int)n; i++) #define FOR(n) for(int i = 0; i < (int)n; i++) #define repi(i,a,b) for(int i = (int)a; i < (int)b; i++) #define pb push_back #define m0(x) memset(x,0,sizeof(x)) #define fill(x,y) memset(x,y,sizeof(x)) #define bg begin() #define ed end() #define all(x) x.bg,x.ed //#define mp make_pair #define vi vector<int> #define vvi vector<vi> #define vll vector<ll> #define vvll vector<vll> #define vs vector<string> #define vvs vector<vs> #define vc vector<char> #define vvc vector<vc> #define pii pair<int,int> #define pllll pair<ll,ll> #define vpii vector<pair<int,int>> #define vpllll vector<pair<ll,ll>> #define vpis vector<pair<int,string>> #define vplls vector<pair<ll, string>> #define vpsi vector<pair<string, int>> #define vpsll vector<pair<string, ll>> template<typename T> void chmax(T &a, const T &b) {a = (a > b? a : b);} template<typename T> void chmin(T &a, const T &b) {a = (a < b? a : b);} using ll = long long; using ld = long double; using ull = unsigned long long; const ll INF = numeric_limits<long long>::max() / 2; const ld pi = 3.1415926535897932384626433832795028; const ll mod = 1e9 + 7; int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1}; int dy[] = {0, -1, 0, 1, -1, 1, -1, 1}; #define int long long struct fenwick_tree { int n, sz; vector<int> dat; function<int(int, int)> f = [](int x, int y) {return (x + y) % mod;}; fenwick_tree(int n_) : dat(4*n_, 0), sz(n_) { int x = 1; while(x < n_) x *= 2; n = x; } void add(int i, int x) { i += n - 1; dat[i] += x; while(i > 0) { i = (i - 1) / 2; dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]); } } void insert(int i) { return add(i, 1); } void erase(int i) { return add(i, -1); } void update(int i, int x) { i += n - 1; dat[i] = x; while(i > 0) { i = (i - 1) / 2; dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]); } } int get_sum(int a, int b) { return get_sum_sub(a, b, 0, 0, n); } int get_sum_sub(int a, int b, int k, int l, int r) { if(r <= a || b <= l) { return 0; }else if(a <= l && r <= b) { return dat[k]; }else { int vl = get_sum_sub(a, b, k * 2 + 1, l, (l + r) / 2); int vr = get_sum_sub(a, b, k * 2 + 2, (l + r) / 2, r); return f(vl, vr); } } int get(int i) { return dat[i + n - 1]; } inline void print() { cout << "{ "; for(int i = 0; i < sz; i++) { cout << dat[i + n - 1] << " "; } cout << "}\n"; } }; int two[200100]; void solve() { two[0] = 1; FOR(200099) two[i+1] = two[i]*2%mod; int n; cin >> n; vi a(n); FOR(n) cin >> a[i]; vi val_a = a; sort(all(val_a)); val_a.erase(unique(all(val_a)), val_a.end()); for(auto& e : a) e = (int)(lower_bound(all(val_a), e) - val_a.begin()); // for(auto e : a) cout << e << " "; cout << "\n"; int ans = 0; fenwick_tree f(n+1); fenwick_tree b(n+1); FOR(n) b.add(a[i], two[n-1-i]); FOR(n) { b.add(a[i], -two[n-1-i]); ans += f.get_sum(0, a[i]) * b.get_sum(0, a[i]) % mod; ans += f.get_sum(a[i]+1, n+1) * b.get_sum(a[i]+1, n+1) % mod; ans %= mod; f.add(a[i], two[i]); } cout << ans << endl; } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }