結果
問題 | No.1031 いたずら好きなお姉ちゃん |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>using namespace std;#ifdef LOCAL#include "debug.h"#else#define DEBUG(...)#endiftemplate <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';}