結果

問題 No.1031 いたずら好きなお姉ちゃん
ユーザー risujiroh
提出日時 2020-04-17 21:55:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 159 ms / 3,500 ms
コード長 2,073 bytes
コンパイル時間 2,540 ms
コンパイル使用メモリ 206,444 KB
最終ジャッジ日時 2025-01-09 19:57:59
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif
template <class T> struct disjoint_sparse_table {
vector<vector<T>> t;
disjoint_sparse_table(const vector<T>& v) : t(1, v) {
for (int k = 1, n = v.size(); 1 << k < n; ++k) {
t.push_back(v);
for (int m = 1 << k; m < n; m += 1 << (k + 1)) {
partial_sum(rend(v) - m, rend(v) - (m - (1 << k)),
rend(t[k]) - m, [](T a, T b) { return b * a; });
partial_sum(begin(v) + m, begin(v) + min(m + (1 << k), n),
begin(t[k]) + m, multiplies<>());
}
}
}
T fold(int l, int r) const {
assert(l < r);
if (l == --r) return t[0][l];
int k = __lg(l ^ r);
return t[k][l] * t[k][r];
}
};
struct node {
int mn, mx;
node operator*(node b) const {
return {min(mn, b.mn), max(mx, b.mx)};
}
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<int> p(n);
for (auto&& e : p) {
cin >> e;
--e;
}
long long res = 0;
for (int _ = 2; _--; ) {
vector<node> _v(n);
for (int i = 0; i < n; ++i) {
_v[i] = {p[i], p[i]};
}
disjoint_sparse_table<node> st(_v);
auto nxt = [&](int i, bool gt = true) {
int ok = i + 1, ng = n + 1;
while (ng - ok > 1) {
int mid = (ok + ng) / 2;
if (gt) {
(st.fold(i, mid).mx <= p[i] ? ok : ng) = mid;
} else {
(st.fold(i, mid).mn >= p[i] ? ok : ng) = mid;
}
}
return ok;
};
vector dp(17, vector<int>(n + 1, n));
for (int i = 0; i < n; ++i) {
dp[0][i] = nxt(i);
}
for (int k = 0; k < 16; ++k) {
for (int i = 0; i < n; ++i) {
dp[k + 1][i] = dp[k][dp[k][i]];
}
}
for (int i = 0; i < n; ++i) {
int j = nxt(i, false);
int pos = i;
for (int k = 17; k--; ) {
if (dp[k][pos] < j) {
res += 1 << k;
pos = dp[k][pos];
}
}
}
reverse(begin(p), end(p));
}
cout << res << '\n';
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0