結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 22:01:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 5,932 bytes |
コンパイル時間 | 3,383 ms |
コンパイル使用メモリ | 204,552 KB |
最終ジャッジ日時 | 2025-01-11 22:39:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)#define itn int#define miele(v) min_element(v.begin(), v.end())#define maele(v) max_element(v.begin(), v.end())#define SUM(v) accumulate(v.begin(), v.end(), 0LL)#define lb(a, key) lower_bound(a.begin(),a.end(),key)#define ub(a, key) upper_bound(a.begin(),a.end(),key)#define COUNT(a, key) count(a.begin(), a.end(), key)#define BITCOUNT(x) __builtin_popcount(x)#define pb push_back#define all(x) (x).begin(),(x).end()#define F first#define S secondusing P = pair <int,int>;using WeightedGraph = vector<vector <P>>;using UnWeightedGraph = vector<vector<int>>;using Real = long double;using Point = complex<Real>; //Point and Vector2d is the same!using Vector2d = complex<Real>;const long long INF = 1LL << 60;const int MOD = 1000000007;const double EPS = 1e-15;const double PI=3.14159265358979323846;template <typename T>int getIndexOfLowerBound(vector <T> &v, T x){return lower_bound(v.begin(),v.end(),x)-v.begin();}template <typename T>int getIndexOfUpperBound(vector <T> &v, T x){return upper_bound(v.begin(),v.end(),x)-v.begin();}template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }#define DUMPOUT cerr#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)istream &operator>>(istream &is, Point &p) {Real a, b; is >> a >> b; p = Point(a, b); return is;}template <typename T, typename U>istream &operator>>(istream &is, pair<T,U> &p_var) {is >> p_var.first >> p_var.second;return is;}template <typename T>istream &operator>>(istream &is, vector<T> &vec) {for (T &x : vec) is >> x;return is;}template <typename T, typename U>ostream &operator<<(ostream &os, pair<T, U> &pair_var) {DUMPOUT<<'{';os << pair_var.first;DUMPOUT<<',';os << " "<< pair_var.second;DUMPOUT<<'}';return os;}template <typename T>ostream &operator<<(ostream &os, vector<T> &vec) {DUMPOUT<<'[';for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");DUMPOUT<<']';return os;}template <typename T>ostream &operator<<(ostream &os, vector<vector<T>> &df) {for (auto& vec : df) os<<vec;return os;}template <typename T, typename U>ostream &operator<<(ostream &os, map<T, U> &map_var) {DUMPOUT << "{";repi(itr, map_var) {os << *itr;itr++;if (itr != map_var.end()) DUMPOUT << ", ";itr--;}DUMPOUT << "}";return os;}template <typename T>ostream &operator<<(ostream &os, set<T> &set_var) {DUMPOUT << "{";repi(itr, set_var) {os << *itr;itr++;if (itr != set_var.end()) DUMPOUT << ", ";itr--;}DUMPOUT << "}";return os;}void print() {cout << endl;}template <class Head, class... Tail>void print(Head&& head, Tail&&... tail) {cout << head;if (sizeof...(tail) != 0) cout << " ";print(forward<Tail>(tail)...);}void dump_func() {DUMPOUT << '#'<<endl;}template <typename Head, typename... Tail>void dump_func(Head &&head, Tail &&... tail) {DUMPOUT << head;if (sizeof...(Tail) > 0) DUMPOUT << ", ";dump_func(std::move(tail)...);}#ifdef DEBUG_#define DEB#define dump(...) \DUMPOUT << " " << string(#__VA_ARGS__) << ": " \<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \<< endl \<< " ", \dump_func(__VA_ARGS__)#else#define DEB if (false)#define dump(...)#endifstruct LazySegTree{ // add and maxint n;vector <int> node, lazy;LazySegTree(vector <int> v){int sz = v.size();n = 1;while(n<sz) n*=2;node.resize(2*n-1);lazy.resize(2*n-1, 0);for(int i=0; i<sz; i++) node[i+n-1] = v[i]; //一番下側for(int i=n-2;i>=0;i--) node[i] = max(node[2*i+1], node[2*i+2]);}void eval(int k,int l, int r){if(lazy[k] != 0){node[k] += lazy[k];if(r - l >1){lazy[2*k+1] += lazy[k];lazy[2*k+2] += lazy[k];}lazy[k] = 0;}}void add(int a, int b, int x, int k=0, int l=0, int 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] = max(node[2*k+1], node[2*k+2]);//chmax(node[k], max(node[2*k+1],node[2*k+2]));}}int getmax(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;if(b <= l || r <= a) return -INF;eval(k, l, r);if(a <= l && r <= b) return node[k];int vl = getmax(a, b, 2*k+1, l, (l+r)/2);int vr = getmax(a, b, 2*k+2, (l+r)/2, r);return max(vl, vr);}};signed main(void) { cin.tie(0); ios::sync_with_stdio(false);int n; cin>>n;vector <int> a(n), b(n);vector <int> place(n+10);cin>>a>>b;rep(i, n){place[a[i]] = i;}vector <int> tmp(n);rep(i, n) tmp[i] = i;LazySegTree seg(tmp);int ans = 0;dump(tmp);for(int i=0;i<n;i++){int p = seg.getmax(place[b[i]], place[b[i]]+1);//dump(b[i], p);seg.add(0, place[b[i]], 1);ans += abs(p - i);}print(ans);}