結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2020-07-21 11:53:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 4,163 bytes |
コンパイル時間 | 2,900 ms |
コンパイル使用メモリ | 175,440 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-12-27 12:15:47 |
合計ジャッジ時間 | 5,804 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; template<class T> class SegTree{ private: int n; int m; int depth; T def; vector<T> data; function<T(T,T)> calculate; function<T(T,T)> update; T rec(int l, int r, int node, int node_l, int node_r) { if (node_r <= l || node_l >= r) return def; if (node_l >= l && node_r <= r) return data[node]; int mid = (node_l + node_r) / 2; return calculate( rec(l, r, node * 2, node_l, mid), rec(l, r, node * 2 + 1, mid, node_r)); } void _assign(int index, T val){ index += n; data[index] = update(data[index], val); for(;index /= 2;) data[index] = calculate(data[index * 2],data[index * 2 + 1]); } void _print() { cerr << "["; for(int i = 0; i < m; i++) { cerr << data[i + n] << (i != m - 1 ? "," : "]\n"); } } void _show() { vector<string> res(depth + 1); vector<int> width(depth + 1); width[depth-1] = 3; for(int i = depth-2; i >= 0; i--)width[i] = width[i + 1] * 2 + 2; for(int i = 0; i < depth; i++) { int start = 1<<i, end = 1<<(i + 1); for(int j = start; j < end; j++) { int d = 0, cur = (data[j] == 0 ? 1 : data[j]); while(cur){cur/=10,d++;} int wid = width[i] - d; cerr << '[' << right << string(wid/2,' ') << data[j] << string(wid - wid/2, ' ') << ']'; } cerr << endl; } } int _lower_right(int index, T val) { int lef = index, rig = n; //ooooxx while(rig - lef > 1) { int mid = (rig + lef) / 2; (get(index, mid) < val ? lef : rig) = mid; } return rig; } int _upper_right(int index, T val) { int lef = index, rig = n; //ooooxx while(rig - lef > 1) { int mid = (rig + lef) / 2; (get(index, mid) <= val ? lef : rig) = mid; } return rig; } public: SegTree(vector<T> a, T _def, function<T(T,T)> _calculate, function<T(T,T)> _update): def(_def), calculate(_calculate), update(_update) { m = a.size(); for (n = 1; n < (int) a.size(); n *= 2, depth++); data.resize(n * 2, def); for (int i = 0; i < (int) a.size(); i++) data[i + n] = a[i]; for (int i = n - 1; i >= 1; i--) data[i] = calculate(data[i * 2], data[i * 2 + 1]); } //区間取得 T get(int l,int r){ if(l == r)return def; return rec(l,r,1,0,n); } //一点更新 void assign(int index, T val){ _assign(index, val); } void print() { _print(); } void show() { _show(); } T operator[] (int i){ return data[i + n]; } //get(index, right) >= valとなるような最小のright int lower_right(int index, T val) { return _lower_right(index, val); } //get(index, right) > valとなるような最小のright int upper_right(int index, T val) { return _upper_right(index, val); } }; ll rev(vector<int> a) { int n = a.size(); SegTree<int> tree(vector<int>(n), 0, [](int a, int b){return a + b;}, [](int a, int b){return a + b;}); ll sum = 0; for(int i = 0; i < n; i++) { sum += tree.get(a[i], n + 1); tree.assign(a[i], 1); } return sum; } int main() { int n; cin >> n; vector<int> a(n), p(n); for(int i = 0; i < n; i++)cin >> a[i], a[i]--; for(int i = 0; i < n; i++) { int t; cin >> t; t--; p[t] = i; } for(int i = 0; i < n; i++)a[i] = p[a[i]]; cout << rev(a) << endl; }