Submission #22952457

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <queue>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main(){
  /*標準入力から読み込み*/
  int N;
  cin >> N;
  vector<int>A(N);
  vector<int>B(N);
  for (int i=0; i<N; i++) cin >> A.at(i);
  for (int i=0; i<N; i++) cin >> B.at(i);
  /*加減算処理をなくす*/
  for (int i=0; i<N; i++) A.at(i) += i;
  for (int i=0; i<N; i++) B.at(i) += i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <queue>
#include <iostream>
#include <vector>
#include <map>
using namespace std;




int main(){
	/*標準入力から読み込み*/
	int N;
	cin >> N;
	vector<int>A(N);
	vector<int>B(N);
	for (int i=0; i<N; i++) cin >> A.at(i);
	for (int i=0; i<N; i++) cin >> B.at(i);

	/*加減算処理をなくす*/
	for (int i=0; i<N; i++) A.at(i) += i;
	for (int i=0; i<N; i++) B.at(i) += i;

	/*順列に置き換え*/
	map<int,queue<int>> q;
	for(int i=0;i<N;i++) q[B.at(i)].push(i+1); 
	for(int i=0;i<N;i++){
		if(q[A.at(i)].empty()){   //Aの要素がBになかった時
			cout<< -1 <<endl;  
			return 0;
		}
		int a=q[A.at(i)].front();
		q[A.at(i)].pop();
		A.at(i)=a;
	}

	/*BIT*/
	long long ans=0;
	vector<int>BIT(N+1,0);
	for(int i=N-1;i>=0;i--){
		for(int j=A.at(i);j>0;j-=(j&-j)) ans+=BIT.at(j);
		for(int j=A.at(i);j<=N;j+=(j&-j)) BIT.at(j)++;
    }
	cout<<ans<<endl;

	return 0;	
}

Submission Info

Judge Result