結果
問題 |
No.610 区間賞(Section Award)
|
ユーザー |
![]() |
提出日時 | 2018-06-05 23:38:49 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 285 ms / 2,000 ms |
コード長 | 1,057 bytes |
コンパイル時間 | 2,217 ms |
コンパイル使用メモリ | 170,472 KB |
実行使用メモリ | 9,600 KB |
最終ジャッジ日時 | 2024-06-30 10:09:13 |
合計ジャッジ時間 | 7,223 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include<bits/stdc++.h> #define all(vec) vec.begin(),vec.end() using namespace std; typedef long long int ll; typedef pair<int,int> P; const ll MOD=1000000007; const ll INF=1000000010; const ll LINF=4000000000000000010LL; const int MAX=310; const double EPS=1e-9; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int a[100010],b[100010]; struct BinaryIndexedTree{ vector<int> bit; BinaryIndexedTree(int siz){ bit.assign(++siz,0); } int sum(int k){ int ret=0; for(++k;k>0;k-=k&-k){ ret+=bit[k]; } return ret; } void add(int k,int x){ for(++k;k<bit.size();k+=k&-k){ bit[k]+=x; } } }; int main(){ int n;cin>>n; map<int,int> mp; BinaryIndexedTree bit(n+1); for(int i=0;i<n;i++){ cin>>a[i]; mp[a[i]]=i+1; } for(int j=0;j<n;j++){ cin>>b[j]; } vector<int> ans; for(int i=0;i<n;i++){ if(bit.sum(n)-bit.sum(mp[b[i]])==0){ ans.push_back(b[i]); } bit.add(mp[b[i]],1); } sort(all(ans)); for(auto a:ans){ cout<<a<<endl; } return 0; }