結果
問題 | No.1975 Zigzag Sequence |
ユーザー |
![]() |
提出日時 | 2022-06-10 22:58:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 292 ms / 2,000 ms |
コード長 | 5,960 bytes |
コンパイル時間 | 5,561 ms |
コンパイル使用メモリ | 320,160 KB |
実行使用メモリ | 17,324 KB |
最終ジャッジ日時 | 2024-09-21 06:45:28 |
合計ジャッジ時間 | 11,536 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;// using mint = modint998244353;// using mint = modint;//mint::set_mod(MOD);const long long MOD = 1000000007;// const long long MOD = 998244353;#include <bits/stdc++.h>#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)#define repeq(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); i++)#define repreq(i, a, b) for (ll i = (ll)(a); i >= (ll)(b); i--)#define each(a, b) for (auto &(a) : (b))#define endl '\n' // fflush(stdout);#define cYes cout << "Yes" << endl#define cNo cout << "No" << endl#define sortr(v) sort(v, greater<>())#define pb push_back#define mp make_pair#define mt make_tuple#define tget(a, b) get<b>(a)#define FI first#define SE second#define ALL(v) (v).begin(), (v).end()#define INFLL 3000000000000000100LL#define INF 1000000100#define PI acos(-1.0L)#define TAU (PI * 2.0L)using namespace std;typedef long long ll;typedef pair<ll, ll> Pll;typedef tuple<ll, ll, ll> Tlll;typedef vector<int> Vi;typedef vector<Vi> VVi;typedef vector<ll> Vl;typedef vector<Vl> VVl;typedef vector<VVl> VVVl;typedef vector<Tlll> VTlll;typedef vector<mint> Vm;typedef vector<Vm> VVm;typedef vector<string> Vs;typedef vector<double> Vd;typedef vector<char> Vc;typedef vector<bool> Vb;typedef vector<Pll> VPll;typedef priority_queue<ll> PQl;typedef priority_queue<ll, vector<ll>, greater<ll>> PQlr;/* print */template <typename T>ostream &operator<<(ostream &os, const vector<T> &V) {int N = V.size();if (N == 0) {os << endl;return os;}rep(i, 0, N - 1) { os << V[i] << ' '; }os << V[N - 1] << endl;return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &V) {int N = V.size();rep(i, 0, N) os << V[i];return os;}template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> const &P) {os << P.FI << ' ' << P.SE;return os;}ostream &operator<<(ostream &os, mint const &M) {os << M.val();return os;}/* useful */template <typename T>void Vin(vector<T> &v) {int n = v.size();rep(i, 0, n) cin >> v[i];}template <typename T>int SMALLER(vector<T> &a, T x) {return lower_bound(a.begin(), a.end(), x) - a.begin();}template <typename T>int orSMALLER(vector<T> &a, T x) {return upper_bound(a.begin(), a.end(), x) - a.begin();}template <typename T>int BIGGER(vector<T> &a, T x) {return a.size() - orSMALLER(a, x);}template <typename T>int orBIGGER(vector<T> &a, T x) {return a.size() - SMALLER(a, x);}template <typename T>int COUNT(vector<T> &a, T x) {return upper_bound(ALL(a), x) - lower_bound(ALL(a), x);}template <typename T>bool chmax(T &a, T b) {if (a < b) {a = b;return 1;}return 0;}template <typename T>bool chmin(T &a, T b) {if (a > b) {a = b;return 1;}return 0;}template <typename T>void press(T &v) {v.erase(unique(ALL(v)), v.end());}template <typename T>vector<int> zip(vector<T> b) {pair<T, int> p[b.size() + 10];int a = b.size();vector<int> l(a);for (int i = 0; i < a; i++) p[i] = mp(b[i], i);sort(p, p + a);int w = 0;for (int i = 0; i < a; i++) {if (i && p[i].first != p[i - 1].first) w++;l[p[i].second] = w;}return l;}template <typename T>vector<T> vis(vector<T> &v) {vector<T> S(v.size() + 1);rep(i, 1, S.size()) S[i] += v[i - 1] + S[i - 1];return S;}ll dem(ll a, ll b) { return ((a + b - 1) / (b)); }ll dtoll(double d, int g) { return round(d * pow(10, g)); }const double EPS = 1e-10;void init() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cout << fixed << setprecision(12);}// Comm + K -> Comm + 0// Comm + K -> Comm + C = add//// Comm + K -> Comm + U = del///********************************** START **********************************/mint st_add(mint a, mint b) { return a + b; }mint st_zero() { return 0; }struct RAQ {int n;segtree<mint, st_add, st_zero> st;RAQ(int input, mint init = 0) {n = input;st = segtree<mint, st_add, st_zero>(vector<mint>(n + 1, init));}void set(int i, mint k) { apply(i, i + 1, k - get(i)); }void apply(int l, int r, mint val) {st.set(l, st.get(l) + val);st.set(r, st.get(r) - val);}mint get(int i) { return st.prod(0, i + 1); }void out() {for (int i = 0; i < n; i++) cout << get(i) << " \n"[i == n - 1];}void err() {for (int i = 0; i < n; i++) cerr << get(i) << " \n"[i == n - 1];}mint operator[](int i) { return get(i); }};void sol() {int n;cin >> n;Vl a(n);Vin(a);// cerr << zip(a) << endl;mint ans = 0;auto f = [&]() {map<ll, Vi> ma;mint pre = 0;RAQ st(n), str(n);rep(i, 0, n) { ma[a[i]].pb(i); }for (auto p : ma) {auto key = p.first;auto val = p.second;rep(i, 0, val.size()) {mint l, r, s;l = st[val[i]];// s = st[n - 1];// r = s - l;// r /= pow_mod(2, val[i] + 1, MOD);mint lr, rr, sr;lr = str[val[i]];sr = str[n - 1];rr = sr - lr;pre += l * rr;// /cerr << lr << ' ' << r << endl;}rep(i, 0, val.size()) {mint ad = pow_mod(2, val[i], MOD);st.apply(val[i], n, ad);mint adr = pow_mod(2, n - 1 - val[i], MOD);str.apply(val[i], n, adr);}}return pre;};ans += f();rep(i, 0, n) a[i] *= -1;ans += f();cout << ans << endl;}int main() {init();int q = 1;// cin >> q;while (q--) sol();return 0;}