結果
問題 | No.1371 交換門松列・松 |
ユーザー | hitonanode |
提出日時 | 2021-01-29 22:16:13 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 57 ms / 4,000 ms |
コード長 | 3,016 bytes |
コンパイル時間 | 2,139 ms |
コンパイル使用メモリ | 211,532 KB |
実行使用メモリ | 14,888 KB |
最終ジャッジ日時 | 2024-06-27 08:31:25 |
合計ジャッジ時間 | 4,019 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 1 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 1 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 39 ms
13,220 KB |
testcase_19 | AC | 39 ms
13,348 KB |
testcase_20 | AC | 39 ms
14,120 KB |
testcase_21 | AC | 38 ms
13,476 KB |
testcase_22 | AC | 38 ms
14,500 KB |
testcase_23 | AC | 57 ms
14,368 KB |
testcase_24 | AC | 56 ms
13,988 KB |
testcase_25 | AC | 56 ms
14,888 KB |
testcase_26 | AC | 55 ms
13,472 KB |
testcase_27 | AC | 53 ms
13,988 KB |
testcase_28 | AC | 55 ms
14,500 KB |
testcase_29 | AC | 54 ms
14,372 KB |
testcase_30 | AC | 54 ms
13,604 KB |
testcase_31 | AC | 55 ms
13,344 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> lohi(N); vector<light_forward_list<pint>> bged(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]); } lohi[i] = make_pair(lo, hi); bged[lo].push_front(pint(A[i], 1)); if (hi < N) bged[hi].push_front(pint(A[i], -1)); } uint64_t ret = 0; REP(a, N) { for (auto [b, v] : bged[a]) { bit.add(b, v); } auto [l, r] = lohi[pos[a]]; ret += bit.sum(l, r); } cout << (ret - N) / 2 << '\n'; }