結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー | koyopro |
提出日時 | 2020-07-17 21:25:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 2,305 bytes |
コンパイル時間 | 1,233 ms |
コンパイル使用メモリ | 156,084 KB |
実行使用メモリ | 14,044 KB |
最終ジャッジ日時 | 2023-08-19 23:29:19 |
合計ジャッジ時間 | 4,683 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
6,016 KB |
testcase_01 | AC | 2 ms
5,472 KB |
testcase_02 | AC | 2 ms
5,428 KB |
testcase_03 | AC | 110 ms
13,072 KB |
testcase_04 | AC | 126 ms
13,840 KB |
testcase_05 | AC | 108 ms
12,676 KB |
testcase_06 | AC | 96 ms
12,648 KB |
testcase_07 | AC | 133 ms
13,856 KB |
testcase_08 | AC | 5 ms
5,808 KB |
testcase_09 | AC | 47 ms
10,216 KB |
testcase_10 | AC | 83 ms
13,860 KB |
testcase_11 | AC | 2 ms
5,492 KB |
testcase_12 | AC | 130 ms
13,864 KB |
testcase_13 | AC | 132 ms
14,044 KB |
testcase_14 | AC | 129 ms
13,748 KB |
testcase_15 | AC | 2 ms
5,704 KB |
testcase_16 | AC | 2 ms
5,432 KB |
testcase_17 | AC | 2 ms
5,476 KB |
testcase_18 | AC | 2 ms
5,432 KB |
testcase_19 | AC | 2 ms
5,564 KB |
testcase_20 | AC | 2 ms
5,472 KB |
testcase_21 | AC | 2 ms
5,692 KB |
testcase_22 | AC | 1 ms
5,424 KB |
testcase_23 | AC | 8 ms
6,044 KB |
testcase_24 | AC | 35 ms
8,520 KB |
testcase_25 | AC | 87 ms
12,288 KB |
testcase_26 | AC | 16 ms
6,884 KB |
testcase_27 | AC | 47 ms
8,984 KB |
testcase_28 | AC | 69 ms
10,052 KB |
testcase_29 | AC | 90 ms
12,480 KB |
testcase_30 | AC | 123 ms
13,480 KB |
testcase_31 | AC | 23 ms
7,520 KB |
testcase_32 | AC | 15 ms
6,544 KB |
testcase_33 | AC | 103 ms
12,952 KB |
testcase_34 | AC | 2 ms
5,600 KB |
testcase_35 | AC | 2 ms
5,488 KB |
testcase_36 | AC | 1 ms
5,440 KB |
testcase_37 | AC | 2 ms
5,452 KB |
testcase_38 | AC | 2 ms
5,636 KB |
testcase_39 | AC | 2 ms
5,752 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define REP1(i, n) for(int i=1; i<=(n); i++) #define RREP1(i, n) for(int i=(n); i>=1; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define out(...) printf(__VA_ARGS__) #if DEBUG #define debug(...) printf(__VA_ARGS__) #else #define debug(...) /* ... */ #endif template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} void solve(); signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; } /*================================*/ #if DEBUG #define SIZE 100 #else #define SIZE 223450 #endif int N,Q,K; int A[SIZE],B[SIZE],C[SIZE]; map<int,int> M; template<typename T> class ST { using F = function<T(T, T)>; int size; T init; F f; vector<T> seg; int depth = 0; public: ST(int size, T init, F f): size(size), init(init), f(f) { while (1<<depth < size) depth++; seg.assign(2<<depth, init); } void update(int k, T t) { k += 1 << depth; seg[k] = t; while(k>>=1) seg[k] = f(seg[2*k], seg[2*k+1]); } T query(int a, int b) { a += 1<<depth; b += 1<<depth; T l = init; T r = init; while(a < b) { if (a & 1) l = f(l, seg[a++]); if (b & 1) r = f(r, seg[--b]); a >>= 1; b >>= 1; } return f(l, r); } T operator[] (int k) { return seg[k + (1<<depth)]; } }; void solve() { cin>>N; REP(i,N)cin>>A[i]; REP(i,N) { M[A[i]]=i; } int b; REP(i,N) { cin>>b; B[i]=M[b]; } auto st = ST<int>(N,0,[](int a,int b){return a+b;}); int ans = 0; REP(i,N) { ans += st.query(B[i]+1, N); st.update(B[i], 1); } cout << ans << endl; }