結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 2020-07-17 21:45:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 2,330 bytes |
コンパイル時間 | 2,249 ms |
コンパイル使用メモリ | 200,432 KB |
最終ジャッジ日時 | 2025-01-11 22:32:14 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
/*** author: yuji9511 ***/#include <bits/stdc++.h>using namespace std;using ll = long long;using lpair = pair<ll, ll>;const ll MOD = 1e9+7;const ll INF = 1e18;#define rep(i,m,n) for(ll i=(m);i<(n);i++)#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};void print() {}template <class H,class... T>void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}struct AddLazySegmentTree {private:ll n;vector<ll> node, lazy;public:AddLazySegmentTree(vector<ll> v) {ll sz = (ll)v.size();n = 1; while(n < sz) n *= 2;node.resize(2*n-1);lazy.resize(2*n-1, 0);for(ll i=0; i<sz; i++) node[i+n-1] = v[i];for(ll i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];}void eval(ll k, ll l, ll r) {if(lazy[k] != 0) {node[k] += lazy[k] * (r-l);if(r - l > 1) {lazy[2*k+1] += lazy[k];lazy[2*k+2] += lazy[k];}lazy[k] = 0;}}void add(ll a, ll b, ll x, ll k=0, ll l=0, ll r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return;if(a <= l && r <= b) {lazy[k] += x;eval(k, l, r);}else {add(a, b, x, 2*k+1, l, (l+r)/2);add(a, b, x, 2*k+2, (l+r)/2, r);node[k] = node[2*k+1] + node[2*k+2];}}ll getsum(ll a, ll b, ll k=0, ll l=0, ll r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a) return 0;if(a <= l && r <= b) return node[k];ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);return vl + vr;}};void solve(){ll N;cin >> N;ll a[100100], b[100010];rep(i,0,N) cin >> a[i];rep(i,0,N) cin >> b[i];ll ps[100010] = {};rep(i,0,N) ps[a[i]] = i;ll ans = 0;vector<ll> v(N+1,0);AddLazySegmentTree sg(v);rep(i,0,N){ll n = b[i];ll pos_a = ps[n] + sg.getsum(ps[n], ps[n]+1);ans += abs(pos_a - i);sg.add(0, ps[n], 1);}print(ans);}int main(){cin.tie(0);ios::sync_with_stdio(false);solve();}