結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2023-10-09 19:27:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,723 bytes |
コンパイル時間 | 2,101 ms |
コンパイル使用メモリ | 200,244 KB |
最終ジャッジ日時 | 2025-02-17 06:28:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(),(v).end() #define pb(a) push_back(a) #define rep(i, n) for(int i=0;i<n;i++) #define foa(e, v) for(auto& e : v) using ll = long long; const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (1LL << 60); #define dout(a) cout<<fixed<<setprecision(10)<<a<<endl; struct SegmentTree { private: ll n; vector<ll> node; ll ID = 0; // min -> INF, max, sum -> 0 inline ll func(ll a, ll b){return a + b;} ///////// public: SegmentTree(vector<ll> v) { int sz = v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, ID); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = func(node[2*i+1], node[2*i+2]); } void update(ll x, ll val) { x += (n - 1); node[x] = val; while(x > 0) { x = (x - 1) / 2; node[x] = func(node[2*x+1], node[2*x+2]); } } ll get(ll a, ll b, ll k=0, ll l=0, ll r=-1) { if(r < 0) r = n; if(r <= a || b <= l) return ID; if(a <= l && r <= b) return node[k]; ll vl = get(a, b, 2*k+1, l, (l+r)/2); ll vr = get(a, b, 2*k+2, (l+r)/2, r); return func(vl, vr); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<int> ord1(n), ord(n); rep(i, n) { int a; cin >> a; ord1[a - 1] = i; } rep(i, n) { int a; cin >> a; ord[ord1[a - 1]] = i; } ll ans = 0; SegmentTree seg(vector<ll> (n, 0)); foa(e, ord) { ans += seg.get(e, n); seg.update(e, 1); } cout << ans << endl; return 0; }