結果
問題 | No.1371 交換門松列・松 |
ユーザー | hitonanode |
提出日時 | 2021-01-29 22:17:48 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 52 ms / 4,000 ms |
コード長 | 3,055 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 211,516 KB |
実行使用メモリ | 12,080 KB |
最終ジャッジ日時 | 2024-06-27 08:33:51 |
合計ジャッジ時間 | 3,912 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 36 ms
11,956 KB |
testcase_19 | AC | 37 ms
11,828 KB |
testcase_20 | AC | 36 ms
11,956 KB |
testcase_21 | AC | 36 ms
11,948 KB |
testcase_22 | AC | 37 ms
11,952 KB |
testcase_23 | AC | 50 ms
12,076 KB |
testcase_24 | AC | 50 ms
11,952 KB |
testcase_25 | AC | 52 ms
12,080 KB |
testcase_26 | AC | 50 ms
11,956 KB |
testcase_27 | AC | 49 ms
12,076 KB |
testcase_28 | AC | 49 ms
11,952 KB |
testcase_29 | AC | 49 ms
11,952 KB |
testcase_30 | AC | 50 ms
11,948 KB |
testcase_31 | AC | 49 ms
11,948 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define REP(i, n) FOR(i,0,n) template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } // 0-indexed BIT (binary indexed tree / Fenwick tree) (i : [0, len)) template <typename T> struct BIT { int n; std::vector<T> data; BIT(int len = 0) : n(len), data(len) {} void reset() { std::fill(data.begin(), data.end(), T(0)); } void add(int pos, T v) { // a[pos] += v pos++; while (pos > 0 and pos <= n) data[pos - 1] += v, pos += pos & -pos; } T sum(int k) const { // a[0] + ... + a[k - 1] T res = 0; while (k > 0) res += data[k - 1], k -= k & -k; return res; } T sum(int l, int r) const { return sum(r) - sum(l); } // a[l] + ... + a[r - 1] }; // Simple forward_list for MLE-sensitive situations // Verify: <http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_D> template <typename T> struct light_forward_list { static std::vector<unsigned> ptr; static std::vector<T> val; unsigned head; light_forward_list() : head(0) {} void push_front(T x) { ptr.push_back(head), val.push_back(x); head = ptr.size() - 1; } struct iterator { unsigned p; iterator operator++() { return {p = ptr[p]}; } T &operator*() { return val[p]; } bool operator!=(const iterator &rhs) { return p != rhs.p; } }; iterator begin() { return {head}; } iterator end() { return {0}; } }; template <typename T> std::vector<unsigned> light_forward_list<T>::ptr = {0}; template <typename T> std::vector<T> light_forward_list<T>::val = {T()}; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (auto &a : A) cin >> a, a--; vector<int> pos(N); REP(i, N) pos[A[i]] = i; BIT<int> bit(N + 1); using pint = pair<int, int>; vector<pint> a2lohi(N); vector<light_forward_list<int>> bg(N + 1); vector<light_forward_list<int>> ed(N + 1); REP(i, N) { bool md = false; int lo = 0, hi = N; if (i == 0) { md = (A[i + 1] < A[i]); } else { md = (A[i - 1] < A[i]); } if (md) { hi = N; if (i) chmax(lo, A[i - 1] + 1); if (i + 1 < N) chmax(lo, A[i + 1] + 1); } else { lo = 0; if (i) chmin(hi, A[i - 1]); if (i + 1 < N) chmin(hi, A[i + 1]); } a2lohi[A[i]] = make_pair(lo, hi); bg[lo].push_front(A[i]); if (hi < N) ed[hi].push_front(A[i]); } uint64_t ret = 0; REP(a, N) { for (auto b : bg[a]) bit.add(b, 1); for (auto b : ed[a]) bit.add(b, -1); auto [l, r] = a2lohi[a]; ret += bit.sum(l, r); } cout << (ret - N) / 2 << '\n'; }