結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー | Ricky_pon |
提出日時 | 2020-07-17 21:49:04 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 4,347 bytes |
コンパイル時間 | 2,240 ms |
コンパイル使用メモリ | 202,324 KB |
実行使用メモリ | 6,312 KB |
最終ジャッジ日時 | 2023-08-20 00:35:28 |
合計ジャッジ時間 | 4,644 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 30 ms
6,216 KB |
testcase_04 | AC | 34 ms
6,312 KB |
testcase_05 | AC | 30 ms
6,248 KB |
testcase_06 | AC | 28 ms
5,944 KB |
testcase_07 | AC | 33 ms
6,272 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 19 ms
4,576 KB |
testcase_10 | AC | 32 ms
6,312 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 35 ms
6,212 KB |
testcase_13 | AC | 35 ms
6,164 KB |
testcase_14 | AC | 35 ms
6,300 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 1 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,380 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 4 ms
4,376 KB |
testcase_24 | AC | 13 ms
4,380 KB |
testcase_25 | AC | 27 ms
5,984 KB |
testcase_26 | AC | 7 ms
4,376 KB |
testcase_27 | AC | 16 ms
4,616 KB |
testcase_28 | AC | 21 ms
4,924 KB |
testcase_29 | AC | 28 ms
6,068 KB |
testcase_30 | AC | 33 ms
6,188 KB |
testcase_31 | AC | 9 ms
4,380 KB |
testcase_32 | AC | 6 ms
4,376 KB |
testcase_33 | AC | 29 ms
6,244 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 2 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,380 KB |
testcase_39 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> #define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i)) #define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i)) #define rep(i, n) For((i), 0, (n)) #define rrep(i, n) rFor((i), (n), 0) #define fi first #define se second using namespace std; typedef long long lint; typedef unsigned long long ulint; typedef pair<int, int> pii; typedef pair<lint, lint> pll; template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;} template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;} template<class T> T div_floor(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>=0 ? a/b : (a+1)/b-1; } template<class T> T div_ceil(T a, T b){ if(b < 0) a *= -1, b *= -1; return a>0 ? (a-1)/b+1 : a/b; } constexpr lint mod = 1000000007; constexpr lint INF = mod * mod; constexpr int MAX = 200010; template<typename T, typename E, typename F, typename G> struct SegTree{ int sz = 1, seq_sz; T et; F f; G g; vector<T> node; SegTree(int sz_, T et, F f, G g): seq_sz(sz_), et(et), f(f), g(g){ while(sz<sz_) sz <<= 1; node.resize(sz<<1, et); } void build(vector<T> &a){ rep(i, a.size()) node[i+sz] = a[i]; rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]); } void build(T x){ rep(i, seq_sz) node[i+sz] = x; rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]); } void update(int i, E x){ i += sz; node[i] = g(node[i], x); i >>= 1; while(i){ node[i] = f(node[i<<1], node[(i<<1)+1]); i >>= 1; } } T query(int l, int r){ T vl = et, vr = et; for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){ if(l&1) vl = f(vl, node[l++]); if(r&1) vr = f(node[--r], vr); } return f(vl, vr); } int search_left(int l, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){ T sum = et; for(l+=sz; ; l>>=1){ if(check(f(sum, node[l]), val)){ while(l < sz){ if(check(f(sum, node[l<<1]), val)) l <<= 1; else{ sum = f(sum, node[l<<1]); l = (l<<1) + 1; } } return l-sz; } if(__builtin_popcount(l+1) == 1) return seq_sz; if(l&1) sum = f(sum, node[l++]); } } int search_right(int r, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){ T sum = et; for(r+=sz; ; r>>=1){ if(check(f(sum, node[r]), val)){ while(r < sz){ if(check(f(node[(r<<1)+1], sum), val)) r = (r<<1) + 1; else{ sum = f(node[(r<<1)+1], sum); r<<=1; } } return r-sz; } if(__builtin_popcount(r) == 1) return -1; if(!(r&1)) sum = f(node[r--], sum); } } int lower_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){ auto check = [&cmp](auto a, auto b){return !cmp(a, b);}; return search_left(l, val, cmp, check); } int upper_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){ auto check = [&cmp](auto a, auto b){return cmp(b, a);}; return search_left(l, val, cmp, check); } int lower_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){ auto check = [&cmp](auto a, auto b){return !cmp(b, a);}; return search_right(l, val, cmp, check); } int upper_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){ auto check = [&cmp](auto a, auto b){return cmp(a, b);}; return search_right(l, val, cmp, check); } }; int main(){ int n; scanf("%d", &n); int a[n], b[n], cnv[n]; rep(i, n) scanf("%d", &a[i]), --a[i]; rep(i, n) scanf("%d", &b[i]), --b[i], cnv[b[i]] = i; rep(i, n) a[i] = cnv[a[i]]; SegTree<lint, lint, decltype(plus<>()), decltype(plus<>())> st(n, 0, plus<>(), plus<>()); lint ans = 0; rep(i, n){ ans += st.query(a[i], n); st.update(a[i], 1); } printf("%lld\n", ans); }