結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:17:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 1,162 bytes |
コンパイル時間 | 2,190 ms |
コンパイル使用メモリ | 196,676 KB |
最終ジャッジ日時 | 2025-01-11 22:51:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)#define rrep(i,n) RREP(i,n-1,0)#define all(v) v.begin(), v.end()const int inf = 1e9+7;const ll longinf = 1LL<<60;const ll mod = 1e9+7;template< typename T >struct BinaryIndexedTree {vector< T > data;BinaryIndexedTree(int sz) {data.assign(++sz, 0);}T sum(int k) {T ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return (ret);}void add(int k, T x) {for(++k; k < data.size(); k += k & -k) data[k] += x;}};int main() {cin.tie(0);ios::sync_with_stdio(false);int n; cin >> n;vector<int> A(n), B(n), pos(n);rep(i, n) {cin >> A[i]; A[i]--;pos[A[i]] = i;}rep(i, n) { cin >> B[i]; B[i]--; }vector<int> C(n);rep(i, n) C[pos[B[i]]] = i;BinaryIndexedTree<int> bit(n);vector<int> bias(n);rrep(i, n) {bias[C[i]] = bit.sum(C[i]);bit.add(C[i], 1);}ll ans = 0;rep(i, n) {ans += i+bias[C[i]]-C[i];}cout << ans << "\n";return 0;}