結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー sanada_atcoder
提出日時 2020-07-17 21:38:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 2,000 ms
コード長 3,752 bytes
コンパイル時間 998 ms
コンパイル使用メモリ 103,324 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-11-29 22:22:27
合計ジャッジ時間 3,305 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<random>
#include<iomanip>
#include<queue>
#include<stack>
#include<assert.h>
#include<time.h>
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ggr getchar();getchar();return 0;
#define prique priority_queue
constexpr auto mod = 1000000007;
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
template<class T> inline void chmax(T& a, T b) {
a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
a = std::min(a, b);
}
//combination(N使
const int MAX = 2330000;
int fac[MAX], finv[MAX], inv[MAX];
//
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
long long COMB(int n, int k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
bool prime(int n) {
int cnt = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0)cnt++;
}
if (cnt != 1)return false;
else return n != 1;
}
int gcd(int x, int y) {
if (y == 0)return x;
return gcd(y, x % y);
}
int lcm(int x, int y) {
return x / gcd(x, y) * y;
}
//Ncombination)
int mod_pow(int x, int y, int m) {
int res = 1;
while (y) {
if (y & 1) {
res = res * x % m;
}
x = x * x % m;
y >>= 1;
}
return res;
}
int kai(int x, int y) {
int res = 1;
for (int i = x - y + 1; i <= x; i++) {
res *= (i % mod); res %= mod;
}
return res;
}
int comb(int x, int y) {
if (y > x)return 0;
return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
//UnionFind
class UnionFind {
protected:
int* par, * rank, * size;
public:
UnionFind(unsigned int size) {
par = new int[size];
rank = new int[size];
this->size = new int[size];
rep(i, size) {
par[i] = i;
rank[i] = 0;
this->size[i] = 1;
}
}
int find(int n) {
if (par[n] == n)return n;
return par[n] = find(par[n]);
}
void unite(int n, int m) {
n = find(n);
m = find(m);
if (n == m)return;
if (rank[n] < rank[m]) {
par[n] = m;
size[m] += size[n];
}
else {
par[m] = n;
size[n] += size[m];
if (rank[n] == rank[m])rank[n]++;
}
}
bool same(int n, int m) {
return find(n) == find(m);
}
int getsize(int n) {
return size[find(n)];
}
};
int dight(int n) {
int ans = 1;
while (n >= 10) {
n /= 10;
ans++;
}
return ans;
}
int dight_sum(int n) {
int sum = 0;
rep(i, 20)sum += (n % (int)pow(10, i + 1)) / (pow(10, i));
return sum;
}
int dight_min(int n) {
int ans = 9;
while (n >= 10) {
ans = min(ans, n % 10);
n /= 10;
}
ans = min(ans, n);
return ans;
}
int dight_max(int n) {
int ans = 0;
while (n >= 10) {
ans = max(ans, n % 10);
n /= 10;
}
ans = max(ans, n);
return ans;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
int bit[114514];
int n;
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= i & -i;
}
return s;
}
void add(int i, int x) {
while (i <= n) {
bit[i] += x;
i += i & -i;
}
}
int a[114514], b[114514];
int memo[114514];
signed main() {
cin >> n;
rep(i, n)cin >> a[i];
rep(i, n)cin >> b[i];
rep(i, n)memo[a[i] - 1] = i + 1;
rep(i, n)b[i] = memo[b[i] - 1];
int ans = 0;
rep(i, n) {
ans += i - sum(b[i]);
add(b[i], 1);
}
cout << ans << endl;
ggr
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0