結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:29:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 77 ms / 2,000 ms |
コード長 | 4,254 bytes |
コンパイル時間 | 1,421 ms |
コンパイル使用メモリ | 114,784 KB |
実行使用メモリ | 6,120 KB |
最終ジャッジ日時 | 2024-11-29 21:31:09 |
合計ジャッジ時間 | 3,408 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
ソースコード
#include <iostream>#include <iomanip>#include <string>#include <stack>#include <vector>#include <complex>#include <math.h>#include <stdio.h>#include <algorithm>#include <utility>#include <functional>#include <iterator>#include <map>#include <set>#include <queue>#include <list>#include <regex>#include <limits>#include <time.h>#include <cstdint>using namespace std;using pii = pair<int,int>;using ll=long long;using ld=long double;#define pb push_back#define mp make_pair#define sc second#define fr first#define stpr setprecision#define cYES cout<<"YES"<<endl#define cNO cout<<"NO"<<endl#define cYes cout<<"Yes"<<endl#define cNo cout<<"No"<<endl#define rep(i,n) for(ll i=0;i<(n);++i)#define Rep(i,a,b) for(ll i=(a);i<(b);++i)#define rrep(i,n) for(ll i=n-1;i>=0;i--)#define rRep(i,a,b) for(ll i=a;i>=b;i--)#define crep(i) for(char i='a';i<='z';++i)#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});#define ALL(x) (x).begin(),(x).end()#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define endl '\n'int ctoi(const char c){if('0' <= c && c <= '9') return (c-'0');return -1;}ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}ll lcm(ll a,ll b){return a*b/gcd(a,b);}constexpr ll MOD=1000000007;constexpr ll INF=1000000011;constexpr ll MOD2=998244353;constexpr ll LINF = 1001002003004005006ll;constexpr ld EPS=10e-8;template <class T, class U> inline bool chmax(T& lhs, const U& rhs) { if (lhs < rhs) { lhs = rhs; return 1; } return 0; }template <class T, class U> inline bool chmin(T& lhs, const U& rhs) { if (lhs > rhs) { lhs = rhs; return 1; } return 0; }template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}template<class T> ostream& operator<<(ostream& os, vector<T>& v){for(auto i=begin(v); i != end(v); ++i){if(i !=begin(v)) os << ' ';os << *i;}return os;}// modinttemplate <std::uint_fast64_t Modulus> class modint {using u64 = std::uint_fast64_t;public:u64 a;constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}constexpr u64 &value() noexcept { return a; }constexpr const u64 &value() const noexcept { return a; }constexpr modint operator+(const modint rhs) const noexcept {return modint(*this) += rhs;}constexpr modint operator-(const modint rhs) const noexcept {return modint(*this) -= rhs;}constexpr modint operator*(const modint rhs) const noexcept {return modint(*this) *= rhs;}constexpr modint operator/(const modint rhs) const noexcept {return modint(*this) /= rhs;}constexpr modint &operator+=(const modint rhs) noexcept {a += rhs.a;if (a >= Modulus) {a -= Modulus;}return *this;}constexpr modint &operator-=(const modint rhs) noexcept {if (a < rhs.a) {a += Modulus;}a -= rhs.a;return *this;}constexpr modint &operator*=(const modint rhs) noexcept {a = a * rhs.a % Modulus;return *this;}constexpr modint &operator/=(modint rhs) noexcept {u64 exp = Modulus - 2;while (exp) {if (exp % 2) {*this *= rhs;}rhs *= rhs;exp /= 2;}return *this;}};ll C[100007],A[100007];ll merge_cnt(vector<int> &a) {int n = a.size();if (n <= 1) { return 0; }ll cnt = 0;vector<int> b(a.begin(), a.begin()+n/2);vector<int> c(a.begin()+n/2, a.end());cnt += merge_cnt(b);cnt += merge_cnt(c);int ai = 0, bi = 0, ci = 0;// merge の処理while (ai < n) {if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {a[ai++] = b[bi++];} else {cnt += n / 2 - bi;a[ai++] = c[ci++];}}return cnt;}vector<int> V;int main(){ll N;cin >> N;rep(i,N){cin >> A[i];C[A[i]]=i+1;}rep(i,N){cin >> A[i];A[i]=C[A[i]];}ll ANS=0;rep(i,N){V.pb(A[i]);}cout << merge_cnt(V) << endl;}