結果
問題 | No.610 区間賞(Section Award) |
ユーザー |
|
提出日時 | 2017-12-10 00:29:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 3,595 bytes |
コンパイル時間 | 2,423 ms |
コンパイル使用メモリ | 207,072 KB |
最終ジャッジ日時 | 2025-01-05 05:06:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include <bits/stdc++.h>#define show(x) cerr << #x << " = " << x << endlusing namespace std;using ll = long long;using pii = pair<int, int>;using vi = vector<int>;template <typename T>ostream& operator<<(ostream& os, const vector<T>& v){os << "sz=" << v.size() << "\n[";for (const auto& p : v) {os << p << ",";}os << "]\n";return os;}template <typename S, typename T>ostream& operator<<(ostream& os, const pair<S, T>& p){os << "(" << p.first << "," << p.second<< ")";return os;}constexpr ll MOD = 1e9 + 7;template <typename T>constexpr T INF = numeric_limits<T>::max() / 100;template <typename Base>class BinaryIndexedTree{public:using T = typename Base::T;using AbelGroup = Base;BinaryIndexedTree(const int n) : data_num(n), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity()) { assert(n > 0); }BinaryIndexedTree(const vector<T>& val) : data_num(val.size()), size(1 << (__lg(2 * data_num - 1))), value(size + 1, AbelGroup::identity()){for (int i = 1; i <= size; i++) {value[i] = val[i - 1];}for (int x = 1; x < size; x++) {value[x + (x & -x)] += value[x];}}T accumulate(const int a) const{assert(0 <= a and a < data_num);int ind = a + 1;T sum = AbelGroup::identity();while (ind > 0) {sum = op(sum, value[ind]);ind &= ind - 1;}return sum;}void add(const int a, const T& val){assert(0 <= a and a < data_num);int ind = a + 1;while (ind <= size) {value[ind] = op(value[ind], val);ind += ind & (-ind);}}void set(const int a, const T& val){const int v = get(a);add(a, op(val, op.inv(v)));}T get(const int a) const{assert(0 <= a and a < data_num);if (a == 0) {return accumulate(a);} else {return op(op.inv(accumulate(a - 1)), accumulate(a));}}int lowerBound(T w) const{if (w <= AbelGroup::identity()) {return 0;}int x = 0;for (int k = ((size == data_num) ? size : size / 2); k > 0; k /= 2) {if (x + k <= size and value[x + k] < w) {w = op(w, op.inv(value[x + k]));x += k;}}return x;}private:const int data_num;const int size;const AbelGroup op{};vector<T> value;};struct Sum {using T = ll;T operator()(const T& a, const T& b) const{return a + b;}T inv(const T& a) const{return -a;}static constexpr T identity(){return 0;}};int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<ll> A(N);for (int i = 0; i < N; i++) {cin >> A[i];A[i]--;}vector<ll> B(N);map<int, int> mp;for (int i = 0; i < N; i++) {cin >> B[i];B[i]--;mp[B[i]] = i;}vector<ll> v(N);for (int i = 0; i < N; i++) {v[i] = mp[A[i]];}vector<int> cand;BinaryIndexedTree<Sum> bit(N);for (int i = N - 1; i >= 0; i--) {if (bit.accumulate(v[i]) == 0) {cand.push_back(A[i]);}bit.add(v[i], 1);}sort(cand.begin(), cand.end());for (const int c : cand) {cout << c + 1 << endl;}return 0;}