結果
| 問題 |
No.1788 Same Set
|
| コンテスト | |
| ユーザー |
 ei1333333
|
| 提出日時 | 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;
}