結果
問題 | No.1788 Same Set |
ユーザー | 👑 hos.lyric |
提出日時 | 2021-12-17 00:54:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 467 ms / 4,000 ms |
コード長 | 7,402 bytes |
コンパイル時間 | 1,268 ms |
コンパイル使用メモリ | 106,296 KB |
実行使用メモリ | 14,216 KB |
最終ジャッジ日時 | 2023-10-12 01:00:41 |
合計ジャッジ時間 | 13,071 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,352 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,352 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,352 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,352 KB |
testcase_09 | AC | 3 ms
5,908 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 137 ms
10,892 KB |
testcase_12 | AC | 194 ms
10,932 KB |
testcase_13 | AC | 222 ms
10,860 KB |
testcase_14 | AC | 286 ms
10,900 KB |
testcase_15 | AC | 355 ms
10,956 KB |
testcase_16 | AC | 392 ms
10,772 KB |
testcase_17 | AC | 307 ms
13,932 KB |
testcase_18 | AC | 374 ms
11,908 KB |
testcase_19 | AC | 223 ms
14,012 KB |
testcase_20 | AC | 216 ms
13,744 KB |
testcase_21 | AC | 370 ms
13,736 KB |
testcase_22 | AC | 402 ms
14,008 KB |
testcase_23 | AC | 354 ms
14,104 KB |
testcase_24 | AC | 406 ms
14,016 KB |
testcase_25 | AC | 467 ms
14,004 KB |
testcase_26 | AC | 454 ms
13,996 KB |
testcase_27 | AC | 273 ms
14,004 KB |
testcase_28 | AC | 459 ms
14,004 KB |
testcase_29 | AC | 431 ms
14,000 KB |
testcase_30 | AC | 275 ms
13,936 KB |
testcase_31 | AC | 446 ms
14,020 KB |
testcase_32 | AC | 376 ms
14,112 KB |
testcase_33 | AC | 391 ms
14,076 KB |
testcase_34 | AC | 416 ms
14,216 KB |
testcase_35 | AC | 404 ms
14,000 KB |
testcase_36 | AC | 403 ms
14,120 KB |
testcase_37 | AC | 402 ms
14,020 KB |
testcase_38 | AC | 394 ms
14,008 KB |
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } // T: monoid representing information of an interval. // T() should return the identity. // T(S s) should represent a single element of the array. // T::push(T &l, T &r) should push the lazy update. // T::merge(const T &l, const T &r) should merge two intervals. template <class T> struct SegmentTreeRange { int logN, n; vector<T> ts; SegmentTreeRange() {} explicit SegmentTreeRange(int n_) { for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {} ts.resize(n << 1); } template <class S> explicit SegmentTreeRange(const vector<S> &ss) { const int n_ = ss.size(); for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {} ts.resize(n << 1); for (int i = 0; i < n_; ++i) at(i) = T(ss[i]); build(); } T &at(int i) { return ts[n + i]; } void build() { for (int u = n; --u; ) merge(u); } inline void push(int u) { ts[u].push(ts[u << 1], ts[u << 1 | 1]); } inline void merge(int u) { ts[u].merge(ts[u << 1], ts[u << 1 | 1]); } // Applies T::f(args...) to [a, b). template <class F, class... Args> void ch(int a, int b, F f, Args &&... args) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return; a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) (ts[aa++].*f)(args...); if (bb & 1) (ts[--bb].*f)(args...); } for (int h = 1; h <= logN; ++h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) merge(aa); } else { if ((aa << h) != a) merge(aa); if ((bb << h) != b) merge(bb); } } } // Calculates the product for [a, b). T get(int a, int b) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return T(); a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } T prodL, prodR, t; for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) { t.merge(prodL, ts[aa++]); prodL = t; } if (bb & 1) { t.merge(ts[--bb], prodR); prodR = t; } } t.merge(prodL, prodR); return t; } // Calculates T::f(args...) of a monoid type for [a, b). // op(-, -) should calculate the product. // e() should return the identity. template <class Op, class E, class F, class... Args> #if __cplusplus >= 201402L auto #else decltype((std::declval<T>().*F())()) #endif get(int a, int b, Op op, E e, F f, Args &&... args) { assert(0 <= a); assert(a <= b); assert(b <= n); if (a == b) return e(); a += n; b += n; for (int h = logN; h; --h) { const int aa = a >> h, bb = b >> h; if (aa == bb) { if ((aa << h) != a || (bb << h) != b) push(aa); } else { if ((aa << h) != a) push(aa); if ((bb << h) != b) push(bb); } } auto prodL = e(), prodR = e(); for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) { if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...)); if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR); } return op(prodL, prodR); } // Find min b s.t. T::f(args...) returns true, // when called for the partition of [a, b) from left to right. // Returns n + 1 if there is no such b. template <class F, class... Args> int findRight(int a, F f, Args &&... args) { assert(0 <= a); assert(a <= n); if ((T().*f)(args...)) return a; if (a == n) return n + 1; a += n; for (int h = logN; h; --h) push(a >> h); for (; ; a >>= 1) if (a & 1) { if ((ts[a].*f)(args...)) { for (; a < n; ) { push(a); if (!(ts[a <<= 1].*f)(args...)) ++a; } return a - n + 1; } ++a; if (!(a & (a - 1))) return n + 1; } } // Find max a s.t. T::f(args...) returns true, // when called for the partition of [a, b) from right to left. // Returns -1 if there is no such a. template <class F, class... Args> int findLeft(int b, F f, Args &&... args) { assert(0 <= b); assert(b <= n); if ((T().*f)(args...)) return b; if (b == 0) return -1; b += n; for (int h = logN; h; --h) push((b - 1) >> h); for (; ; b >>= 1) if ((b & 1) || b == 2) { if ((ts[b - 1].*f)(args...)) { for (; b <= n; ) { push(b - 1); if (!(ts[(b <<= 1) - 1].*f)(args...)) --b; } return b - n - 1; } --b; if (!(b & (b - 1))) return -1; } } }; //////////////////////////////////////////////////////////////////////////////// struct Node { int mn, cnt; int lz; Node() : mn(0), cnt(0), lz(0) {} Node(int val) : mn(val), cnt(1), lz(0) {} void push(Node &l, Node &r) { l.add(lz); r.add(lz); lz = 0; } void merge(const Node &l, const Node &r) { mn = min(l.mn, r.mn); cnt = ((mn == l.mn) ? l.cnt : 0) + ((mn == r.mn) ? r.cnt : 0); } void add(long long val) { mn += val; lz += val; } }; int N; vector<int> A, B; int main() { for (; ~scanf("%d", &N); ) { A.resize(N); for (int i = 0; i < N; ++i) scanf("%d", &A[i]); B.resize(N); for (int i = 0; i < N; ++i) scanf("%d", &B[i]); const int lim = max( *max_element(A.begin(), A.end()), *max_element(B.begin(), B.end()) ) + 1; Int ans = 0; SegmentTreeRange<Node> seg(N); for (int i = 0; i < N; ++i) { seg.at(i) = Node(0); } seg.build(); vector<int> appA(lim, -1), appB(lim, -1); auto add = [&](int x, int val) { int i = appA[x], j = appB[x]; if (i > j) { swap(i, j); } // cerr<<" add "<<x<<" "<<val<<"; "<<i<<" "<<j<<endl; seg.ch(i + 1, j + 1, &Node::add, val); }; for (int i = 0; i < N; ++i) { // cerr<<"i = "<<i<<endl; add(A[i], -1); appA[A[i]] = i; add(A[i], +1); add(B[i], -1); appB[B[i]] = i; add(B[i], +1); const auto res = seg.get(0, i + 1); assert(res.mn == 0); ans += res.cnt; // cerr<<" ans = "<<ans<<endl; } printf("%lld\n", ans); } return 0; }