結果
問題 | No.1788 Same Set |
ユーザー |
![]() |
提出日時 | 2021-12-17 02:23:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,330 ms / 4,000 ms |
コード長 | 6,276 bytes |
コンパイル時間 | 2,611 ms |
コンパイル使用メモリ | 207,604 KB |
最終ジャッジ日時 | 2025-01-27 01:46:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
// だれかおれをたすけてくれ!!!#include<bits/stdc++.h>using namespace std;using int64 = long long;const int mod = 1e9 + 7;// const int mod = 998244353;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in: v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e: t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}/*** @brief Binary-Indexed-Tree(BIT)* @docs docs/binary-indexed-tree.md*/template< typename T >struct BinaryIndexedTree {private:vector< T > data;public:BinaryIndexedTree() = default;explicit BinaryIndexedTree(size_t sz) : data(sz + 1, 0) {}explicit BinaryIndexedTree(const vector< T > &vs) : data(vs.size() + 1, 0) {for(size_t i = 0; i < vs.size(); i++) data[i + 1] = vs[i];for(size_t i = 1; i < data.size(); i++) {size_t j = i + (i & -i);if(j < data.size()) data[j] += data[i];}}void add(int k, const T &x) {for(++k; k < (int) data.size(); k += k & -k) data[k] += x;}T fold(int r) const {T ret = T();for(; r > 0; r -= r & -r) ret += data[r];return ret;}T fold(int l, int r) const {return fold(r) - fold(l);}int lower_bound(T x) const {int i = 0;for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {if(i + k < data.size() && data[i + k] < x) {x -= data[i + k];i += k;}}return i;}int upper_bound(T x) const {int i = 0;for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {if(i + k < data.size() && data[i + k] <= x) {x -= data[i + k];i += k;}}return i;}};const int MAX_V = 4e5;int main() {int N;cin >> N;vector< int > A(N), B(N);cin >> A >> B;for(auto &a: A) --a;for(auto &a: B) --a;int64 ret = 0;vector< int > latte(MAX_V), malta(MAX_V);vector< int > lp(MAX_V, inf), rp(MAX_V, inf);vector< int > pl(MAX_V, -inf), pr(MAX_V, -inf);vector< int > S(N);BinaryIndexedTree< int > bit(N);MFP([&](auto rec, int l, int r) -> void {if(l + 1 >= r) {ret += A[l] == B[l];return;}int m = (l + r) / 2;rec(l, m);rec(m, r);{for(int k = r - 1; k >= m; k--) {lp[A[k]] = k;rp[B[k]] = k;}multiset< int > uku;for(int k = m - 1; k >= l; k--) {if(not latte[A[k]]) {latte[A[k]] = true;if(not malta[A[k]]) {uku.emplace(rp[A[k]]);} else {assert(uku.find(lp[A[k]]) != uku.end());uku.erase(uku.find(lp[A[k]]));}}if(not malta[B[k]]) {malta[B[k]] = true;if(not latte[B[k]]) {uku.emplace(lp[B[k]]);} else {assert(uku.find(rp[B[k]]) != uku.end());uku.erase(uku.find(rp[B[k]]));}}S[k] = uku.empty() ? m : *uku.rbegin();}for(int k = r - 1; k >= m; k--) {lp[A[k]] = inf;rp[B[k]] = inf;}for(int k = m - 1; k >= l; k--) {latte[A[k]] = false;malta[B[k]] = false;}}{for(int k = l; k < m; k++) {pl[A[k]] = k;pr[B[k]] = k;}multiset< int > uku;for(int k = m; k < r; k++) {if(not latte[A[k]]) {latte[A[k]] = true;if(not malta[A[k]]) {uku.emplace(pr[A[k]]);} else {assert(uku.find(pl[A[k]]) != uku.end());uku.erase(uku.find(pl[A[k]]));}}if(not malta[B[k]]) {malta[B[k]] = true;if(not latte[B[k]]) {uku.emplace(pl[B[k]]);} else {assert(uku.find(pr[B[k]]) != uku.end());uku.erase(uku.find(pr[B[k]]));}}S[k] = uku.empty() ? m : *uku.begin();}for(int k = l; k < m; k++) {pl[A[k]] = -inf;pr[B[k]] = -inf;}for(int k = m; k < r; k++) {latte[A[k]] = false;malta[B[k]] = false;}}vector< int > ord(m - l);iota(begin(ord), end(ord), l);sort(begin(ord), end(ord), [&](int a, int b) {return S[a] > S[b];});int p = r - 1;for(auto &a: ord) {while(p >= S[a]) {if(S[p] >= 0) {bit.add(S[p], 1);}--p;}ret += bit.fold(a, N);}while(++p < r) {if(S[p] >= 0) {bit.add(S[p], -1);}}})(0, N);cout << ret << endl;}