結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:49:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 4,347 bytes |
コンパイル時間 | 2,045 ms |
コンパイル使用メモリ | 197,212 KB |
最終ジャッジ日時 | 2025-01-11 22:33:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:129:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 129 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:131:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 131 | rep(i, n) scanf("%d", &a[i]), --a[i]; | ~~~~~^~~~~~~~~~~~~ main.cpp:132:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 132 | rep(i, n) scanf("%d", &b[i]), --b[i], cnv[b[i]] = i; | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))#define rep(i, n) For((i), 0, (n))#define rrep(i, n) rFor((i), (n), 0)#define fi first#define se secondusing namespace std;typedef long long lint;typedef unsigned long long ulint;typedef pair<int, int> pii;typedef pair<lint, lint> pll;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(a>b){a=b; return true;} return false;}template<class T> T div_floor(T a, T b){if(b < 0) a *= -1, b *= -1;return a>=0 ? a/b : (a+1)/b-1;}template<class T> T div_ceil(T a, T b){if(b < 0) a *= -1, b *= -1;return a>0 ? (a-1)/b+1 : a/b;}constexpr lint mod = 1000000007;constexpr lint INF = mod * mod;constexpr int MAX = 200010;template<typename T, typename E, typename F, typename G>struct SegTree{int sz = 1, seq_sz;T et;F f;G g;vector<T> node;SegTree(int sz_, T et, F f, G g): seq_sz(sz_), et(et), f(f), g(g){while(sz<sz_) sz <<= 1;node.resize(sz<<1, et);}void build(vector<T> &a){rep(i, a.size()) node[i+sz] = a[i];rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);}void build(T x){rep(i, seq_sz) node[i+sz] = x;rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);}void update(int i, E x){i += sz;node[i] = g(node[i], x);i >>= 1;while(i){node[i] = f(node[i<<1], node[(i<<1)+1]);i >>= 1;}}T query(int l, int r){T vl = et, vr = et;for(l+=sz, r+=sz; l<r; l>>=1, r>>=1){if(l&1) vl = f(vl, node[l++]);if(r&1) vr = f(node[--r], vr);}return f(vl, vr);}int search_left(int l, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){T sum = et;for(l+=sz; ; l>>=1){if(check(f(sum, node[l]), val)){while(l < sz){if(check(f(sum, node[l<<1]), val)) l <<= 1;else{sum = f(sum, node[l<<1]);l = (l<<1) + 1;}}return l-sz;}if(__builtin_popcount(l+1) == 1) return seq_sz;if(l&1) sum = f(sum, node[l++]);}}int search_right(int r, const T val, function<bool(T, T)> cmp, function<bool(T, T)> check){T sum = et;for(r+=sz; ; r>>=1){if(check(f(sum, node[r]), val)){while(r < sz){if(check(f(node[(r<<1)+1], sum), val)) r = (r<<1) + 1;else{sum = f(node[(r<<1)+1], sum);r<<=1;}}return r-sz;}if(__builtin_popcount(r) == 1) return -1;if(!(r&1)) sum = f(node[r--], sum);}}int lower_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){auto check = [&cmp](auto a, auto b){return !cmp(a, b);};return search_left(l, val, cmp, check);}int upper_bound_left(int l, const T val, function<bool(T, T)> cmp=less<>()){auto check = [&cmp](auto a, auto b){return cmp(b, a);};return search_left(l, val, cmp, check);}int lower_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){auto check = [&cmp](auto a, auto b){return !cmp(b, a);};return search_right(l, val, cmp, check);}int upper_bound_right(int l, const T val, function<bool(T, T)> cmp=greater<>()){auto check = [&cmp](auto a, auto b){return cmp(a, b);};return search_right(l, val, cmp, check);}};int main(){int n;scanf("%d", &n);int a[n], b[n], cnv[n];rep(i, n) scanf("%d", &a[i]), --a[i];rep(i, n) scanf("%d", &b[i]), --b[i], cnv[b[i]] = i;rep(i, n) a[i] = cnv[a[i]];SegTree<lint, lint, decltype(plus<>()), decltype(plus<>())> st(n, 0, plus<>(), plus<>());lint ans = 0;rep(i, n){ans += st.query(a[i], n);st.update(a[i], 1);}printf("%lld\n", ans);}