結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー | keijak |
提出日時 | 2020-07-17 21:26:54 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 2,636 bytes |
コンパイル時間 | 2,249 ms |
コンパイル使用メモリ | 205,096 KB |
実行使用メモリ | 6,276 KB |
最終ジャッジ日時 | 2023-08-19 23:34:06 |
合計ジャッジ時間 | 4,330 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 34 ms
5,764 KB |
testcase_04 | AC | 41 ms
6,152 KB |
testcase_05 | AC | 34 ms
5,636 KB |
testcase_06 | AC | 32 ms
5,420 KB |
testcase_07 | AC | 40 ms
6,148 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 21 ms
4,956 KB |
testcase_10 | AC | 35 ms
6,276 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 40 ms
6,200 KB |
testcase_13 | AC | 41 ms
6,208 KB |
testcase_14 | AC | 39 ms
6,276 KB |
testcase_15 | AC | 1 ms
4,380 KB |
testcase_16 | AC | 1 ms
4,380 KB |
testcase_17 | AC | 2 ms
4,384 KB |
testcase_18 | AC | 1 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 1 ms
4,380 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 5 ms
4,376 KB |
testcase_24 | AC | 13 ms
4,380 KB |
testcase_25 | AC | 29 ms
5,424 KB |
testcase_26 | AC | 8 ms
4,380 KB |
testcase_27 | AC | 17 ms
4,384 KB |
testcase_28 | AC | 24 ms
4,832 KB |
testcase_29 | AC | 32 ms
5,372 KB |
testcase_30 | AC | 39 ms
5,948 KB |
testcase_31 | AC | 10 ms
4,380 KB |
testcase_32 | AC | 7 ms
4,384 KB |
testcase_33 | AC | 32 ms
5,632 KB |
testcase_34 | AC | 1 ms
4,380 KB |
testcase_35 | AC | 2 ms
4,380 KB |
testcase_36 | AC | 2 ms
4,384 KB |
testcase_37 | AC | 2 ms
4,376 KB |
testcase_38 | AC | 1 ms
4,380 KB |
testcase_39 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = long long; using u64 = unsigned long long; #define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i) #ifdef ENABLE_DEBUG template <typename T> void debug(T value) { cerr << value; } template <typename T, typename... Ts> void debug(T value, Ts... args) { cerr << value << ", "; debug(args...); } #define DEBUG(...) \ do { \ cerr << " \033[33m (L" << __LINE__ << ") "; \ cerr << #__VA_ARGS__ << ":\033[0m "; \ debug(__VA_ARGS__); \ cerr << endl; \ } while (0) #else #define debug(...) #define DEBUG(...) #endif template <class Monoid> struct SegTree { using Func = function<Monoid(Monoid, Monoid)>; const Func F; const Monoid UNITY; int size; vector<Monoid> dat; SegTree(int n, const Func f, const Monoid &unity) : F(f), UNITY(unity), size(n), dat(2 * n, unity) {} // Sets i-th value (0-indexed) to x for initial setup. // build() must be called after set() calls. void set(int i, const Monoid &x) { dat[size + i] = x; } void build() { for (int k = size - 1; k > 0; --k) { dat[k] = F(dat[k * 2], dat[k * 2 + 1]); } } // Sets i-th value (0-indexed) to x. void update(int i, const Monoid &x) { int k = size + i; dat[k] = x; while (k > 1) { k >>= 1; dat[k] = F(dat[k * 2], dat[k * 2 + 1]); } } // Queries by [l,r) range (0-indexed, open interval). Monoid fold(int l, int r) { l += size; r += size; Monoid vleft = UNITY, vright = UNITY; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) vleft = F(vleft, dat[l++]); if (r & 1) vright = F(dat[--r], vright); } return F(vleft, vright); } // Queries by a single index (0-indexed). Monoid operator[](int i) { return dat[size + i]; } /* debug */ void print() { for (int i = 0; i < size; ++i) { cout << (*this)[i]; if (i != size - 1) cout << ","; } cout << endl; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> A(n), B(n); for (auto &x : A) { cin >> x; --x; } for (auto &x : B) { cin >> x; --x; } vector<int> ar(n), br(n); REP(i, n) { ar[A[i]] = i; br[B[i]] = i; } SegTree<i64> ast( n, [](i64 x, i64 y) { return x + y; }, 0LL); REP(i, n) { ast.set(i, 1); } ast.build(); i64 steps = 0; REP(i, n) { int k = ar[B[i]]; i64 s = ast.fold(0, k); steps += s; ast.update(k, 0); } cout << steps << endl; }