結果
問題 | No.1788 Same Set |
ユーザー |
![]() |
提出日時 | 2021-12-17 00:24:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 868 ms / 4,000 ms |
コード長 | 2,515 bytes |
コンパイル時間 | 1,877 ms |
コンパイル使用メモリ | 173,784 KB |
実行使用メモリ | 14,164 KB |
最終ジャッジ日時 | 2024-09-14 00:24:35 |
合計ジャッジ時間 | 23,269 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int INF = 1000000; struct monoid{ int mn, cnt; monoid(){ mn = INF, cnt = 0; } monoid(int x){ mn = x, cnt = 1; } }; monoid f(monoid A, monoid B){ monoid C; C.mn = min(A.mn, B.mn); if (A.mn == C.mn){ C.cnt += A.cnt; } if (B.mn == C.mn){ C.cnt += B.cnt; } return C; } struct lazy_segment_tree{ int N; vector<monoid> ST; vector<int> lazy; lazy_segment_tree(int N2){ N = 1; while (N < N2){ N *= 2; } ST = vector<monoid>(N * 2 - 1, monoid(0)); for (int i = N - 2; i >= 0; i--){ ST[i] = f(ST[i * 2 + 1], ST[i * 2 + 2]); } lazy = vector<int>(N * 2 - 1, 0); } void eval(int i){ if (i < N - 1){ lazy[i * 2 + 1] += lazy[i]; lazy[i * 2 + 2] += lazy[i]; } ST[i].mn += lazy[i]; lazy[i] = 0; } void range_add(int L, int R, int x, int i, int l, int r){ eval(i); if (r <= L || R <= l){ return; } else if (L <= l && r <= R){ lazy[i] += x; eval(i); } else { int m = (l + r) / 2; range_add(L, R, x, i * 2 + 1, l, m); range_add(L, R, x, i * 2 + 2, m, r); ST[i] = f(ST[i * 2 + 1], ST[i * 2 + 2]); } } void range_add(int L, int R, int x){ range_add(L, R, x, 0, 0, N); } monoid range_fold(int L, int R, int i, int l, int r){ eval(i); if (r <= L || R <= l){ return monoid(); } else if (L <= l && r <= R){ return ST[i]; } else { int m = (l + r) / 2; return f(range_fold(L, R, i * 2 + 1, l, m), range_fold(L, R, i * 2 + 2, m, r)); } } monoid range_fold(int L, int R){ return range_fold(L, R, 0, 0, N); } }; int main(){ int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++){ cin >> A[i]; A[i]--; } vector<int> B(N); for (int i = 0; i < N; i++){ cin >> B[i]; B[i]--; } long long ans = 0; vector<int> Af(400000, N), Bf(400000, N); lazy_segment_tree ST(N); for (int i = N - 1; i >= 0; i--){ //[Af,Bf) or [Bf,Af) は NG //range add x, rane-min-cnt ST.range_add(min(Af[A[i]], Bf[A[i]]), max(Af[A[i]], Bf[A[i]]), -1); Af[A[i]] = i; ST.range_add(min(Af[A[i]], Bf[A[i]]), max(Af[A[i]], Bf[A[i]]), 1); ST.range_add(min(Af[B[i]], Bf[B[i]]), max(Af[B[i]], Bf[B[i]]), -1); Bf[B[i]] = i; ST.range_add(min(Af[B[i]], Bf[B[i]]), max(Af[B[i]], Bf[B[i]]), 1); monoid res = ST.range_fold(i, N); if (res.mn == 0){ ans += res.cnt; } } cout << ans << endl; }