結果

問題 No.1975 Zigzag Sequence
ユーザー SnowBeenDidingSnowBeenDiding
提出日時 2022-06-10 22:58:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 5,960 bytes
コンパイル時間 5,471 ms
コンパイル使用メモリ 320,852 KB
実行使用メモリ 17,200 KB
最終ジャッジ日時 2024-09-21 06:45:16
合計ジャッジ時間 11,426 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0