結果
| 問題 | No.1371 交換門松列・松 |
| コンテスト | |
| ユーザー |
 minato
|
| 提出日時 | 2021-01-29 21:43:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 214 ms / 4,000 ms |
| コード長 | 10,448 bytes |
| 記録 | |
| コンパイル時間 | 2,598 ms |
| コンパイル使用メモリ | 211,360 KB |
| 最終ジャッジ日時 | 2025-01-18 09:05:54 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vector<T>>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
constexpr char ln = '\n';
template <class Container> inline int SZ(const Container& v) { return int(v.size()); }
template <class T> inline void UNIQUE(vector<T>& v) { v.erase(unique(v.begin(), v.end()), v.end()); }
template <class T1, class T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return true; } return false; }
template <class T1, class T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return true; } return false; }
inline int topbit(ull x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
inline int botbit(ull x) { return x == 0 ? 64 : __builtin_ctzll(x); }
inline int popcount(ull x) { return __builtin_popcountll(x); }
inline int kthbit(ull x, int k) { return (x >> k) & 1; }
inline constexpr long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
const string YESNO[2] = {"NO", "YES"};
const string YesNo[2] = {"No", "Yes"};
inline void YES(bool t = true) { cout << YESNO[t] << "\n"; }
inline void Yes(bool t = true) { cout << YesNo[t] << "\n"; }
template <class T> inline void drop(T x) { cout << x << "\n"; exit(0); }
inline void print() { cout << "\n"; }
template <class T> inline void print(const vector<T>& v) { for (auto it = v.begin(); it != v.end(); ++it) { if (it != v.begin()) { cout << " "; } cout << *it; } print(); }
template <class T, class... Args> inline void print(const T& x, const Args& ... args) { cout << x << " "; print(args...); }
#ifdef MINATO_LOCAL
template <class T1, class T2> ostream& operator<<(ostream& os, pair<T1, T2> p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <size_t N, class TUPLE> void debug_tuple(ostream& os, TUPLE _) { (void)os; (void)_; }
template <size_t N, class TUPLE, class T, class ...Args> void debug_tuple(ostream &os, TUPLE t) { os << (N == 0 ? "" : ", ") << get<N>(t); debug_tuple<N + 1, TUPLE, Args...>(os, t); }
template <class ...Args> ostream& operator<<(ostream& os, tuple<Args...> t) { os << "("; debug_tuple<0, tuple<Args...>, Args...>(os, t); return os << ")"; }
string debug_delim(int& i) { return i++ == 0 ? "" : ", "; }
#define debug_embrace(x) { int i = 0; os << "{"; { x } return os << "}"; }
template <class T> ostream& operator<<(ostream& os, vector<T> v) { debug_embrace( for (T e : v) { os << debug_delim(i) << e; } ) }
template <class T, size_t N> ostream& operator<<(ostream& os, array<T, N> a) { debug_embrace( for (T e : a) { os << debug_delim(i) << e; } ) }
template <class T, size_t N> enable_if_t<!is_same_v<char, remove_cv_t<T>>, ostream>& operator<<(ostream& os, T(&a)[N]) { debug_embrace( for (T e : a) { os << debug_delim(i) << e; } ) }
template <class Key> ostream& operator<<(ostream& os, set<Key> s) { debug_embrace( for (Key e : s) { os << debug_delim(i) << e; }) }
template <class Key, class T> ostream& operator<<(ostream& os, map<Key, T> mp) { debug_embrace( for (auto e : mp) { os << debug_delim(i) << e; }) }
template <class Key> ostream& operator<<(ostream& os, multiset<Key> s) { debug_embrace( for (Key e : s) { os << debug_delim(i) << e; }) }
template <class T> ostream& operator<<(ostream& os, queue<T> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.front(); } ) }
template <class T> ostream& operator<<(ostream& os, deque<T> q) { debug_embrace( for (T e : q) { os << debug_delim(i) << e; } ) }
template <class T> ostream& operator<<(ostream& os, priority_queue<T> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.top(); } ) }
template <class T> ostream& operator<<(ostream& os, priority_queue<T, vector<T>, greater<T>> q) { debug_embrace( for (; !q.empty(); q.pop()) { os << debug_delim(i) << q.top(); } ) }
void debug_out() { cerr << endl; }
template <class T, class... Args> void debug_out(const T& x, const Args& ... args) { cerr << " " << x; debug_out(args...); }
#define debug(...) cerr << __LINE__ << " : [" << #__VA_ARGS__ << "] =", debug_out(__VA_ARGS__)
#else
#define debug(...) (void(0))
#endif
struct fast_ios { fast_ios() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); cerr << fixed << setprecision(7); }; } fast_ios_;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct SuccinctIndexableDictionary {
size_t length;
size_t blocks;
vector<unsigned> bit, sum;
SuccinctIndexableDictionary() = default;
SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
bit.assign(blocks, 0U);
sum.assign(blocks, 0U);
}
void set(int k) {
bit[k >> 5] |= 1U << (k & 31);
}
void build() {
sum[0] = 0U;
for(int i = 1; i < int(blocks); i++) {
sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
}
}
bool operator[](int k) {
return (bool((bit[k >> 5] >> (k & 31)) & 1));
}
int rank(int k) {
return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1)));
}
int rank(bool val, int k) {
return (val ? rank(k) : k - rank(k));
}
};
template<typename T, int MAXLOG>
struct WaveletMatrix {
size_t length;
SuccinctIndexableDictionary matrix[MAXLOG];
int mid[MAXLOG];
WaveletMatrix() = default;
WaveletMatrix(vector<T> v) : length(v.size()) {
vector< T > l(length), r(length);
for(int level = MAXLOG - 1; level >= 0; level--) {
matrix[level] = SuccinctIndexableDictionary(length + 1);
int left = 0, right = 0;
for(int i = 0; i < int(length); i++) {
if(((v[i] >> level) & 1)) {
matrix[level].set(i);
r[right++] = v[i];
} else {
l[left++] = v[i];
}
}
mid[level] = left;
matrix[level].build();
v.swap(l);
for(int i = 0; i < right; i++) {
v[left + i] = r[i];
}
}
}
pair< int, int > succ(bool f, int l, int r, int level) {
return {matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f};
}
// v[k]
T access(int k) {
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
bool f = matrix[level][k];
if(f) ret |= T(1) << level;
k = matrix[level].rank(f, k) + mid[level] * f;
}
return ret;
}
T operator[](const int &k) {
return access(k);
}
// count i s.t. (0 <= i < r) && v[i] == x
int rank(const T &x, int r) {
int l = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
tie(l, r) = succ((x >> level) & 1, l, r, level);
}
return r - l;
}
// k-th(0-indexed) smallest number in v[l,r)
T kth_smallest(int l, int r, int k) {
assert(0 <= k && k < r - l);
T ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
bool f = cnt <= k;
if(f) {
ret |= T(1) << level;
k -= cnt;
}
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// k-th(0-indexed) largest number in v[l,r)
T kth_largest(int l, int r, int k) {
return kth_smallest(l, r, r - l - k - 1);
}
// count i s.t. (l <= i < r) && (v[i] < upper)
int range_freq(int l, int r, T upper) {
int ret = 0;
for(int level = MAXLOG - 1; level >= 0; level--) {
bool f = ((upper >> level) & 1);
if(f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// count i s.t. (l <= i < r) && (lower <= v[i] < upper)
int range_freq(int l, int r, T lower, T upper) {
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
// max v[i] s.t. (l <= i < r) && (v[i] < upper)
T prev_value(int l, int r, T upper) {
int cnt = range_freq(l, r, upper);
return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
}
// min v[i] s.t. (l <= i < r) && (lower <= v[i])
T next_value(int l, int r, T lower) {
int cnt = range_freq(l, r, lower);
return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
}
};
int main() {
int N; cin >> N;
vector<int> arr(N);
rep(i,N) cin >> arr[i];
vec<pii> A,B;
if (arr[0] > arr[1]) {
arr.insert(arr.begin(),0);
if (arr[N] > arr[N-1]) arr.emplace_back(0);
else arr.emplace_back(int(1e6));
for (int i = 1; i <= N; i++) {
if (i&1) A.emplace_back(max(arr[i-1],arr[i+1]),arr[i]);
else B.emplace_back(min(arr[i-1],arr[i+1]),arr[i]);
}
} else {
arr.insert(arr.begin(),int(1e6));
if (arr[N] > arr[N-1]) arr.emplace_back(0);
else arr.emplace_back(int(1e6));
for (int i = 1; i <= N; i++) {
if (~i&1) A.emplace_back(max(arr[i-1],arr[i+1]),arr[i]);
else B.emplace_back(min(arr[i-1],arr[i+1]),arr[i]);
}
}
int M = A.size(), K = B.size();
ll ans = 0;
sort(all(A));
reverse(all(A));
{
debug(A);
vec<int> v(M);
rep(i,M) v[i] = A[i].second;
WaveletMatrix<int, 20> WM(v);
rep(i,M) {
ans += WM.range_freq(i+1,M,A[i].first,int(1e6));
}
debug(ans);
}
sort(all(B));
{
vec<int> v(K);
rep(i,K) v[i] = B[i].second;
WaveletMatrix<int, 20> WM(v);
rep(i,K) {
ans += WM.range_freq(i+1,K,B[i].first);
}
debug(ans);
}
reverse(all(A));
{
vec<int> lb(M);
rep(i,M) lb[i] = A[i].first;
vec<int> v(M);
rep(i,M) v[i] = A[i].second;
WaveletMatrix<int, 20> WM(v);
rep(i,K) {
int k = lower_bound(all(lb),B[i].second) - lb.begin();
ans += WM.range_freq(0,k,B[i].first);
}
}
cout << ans << ln;
}