글 읽기 - 어디가 틀렸는지 도통 모르겠습니다 ㅜ..

isvara 4년 전 0

세그먼트 트리로 구현을 해봤습니다.

어디가 틀린건가요 ㅜ??

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
vector<ll> treeNode;
int N;
int ma[500001];
int re[1000001];
void update(int start, int end, int node, int target, int diff) {
	if (start == end)   
	{
		treeNode[node] = 1;
		return;
	}
 	if (target<start || target>end)return;
	treeNode[node] += diff;
	update(start, (start + end) / 2, node * 2, target, diff);
	update((start + end) / 2 + 1, end, node * 2 + 1, target, diff);
}
ll sum(int start, int end, int node, int NodeLeft, int NodeRight) {
	if (start > NodeRight || end < NodeLeft)
		return 0;
	if (NodeLeft <= start && end <= NodeRight)
		return treeNode[node];
	
 	return treeNode[node]=sum(start, (start + end) / 2, node * 2, NodeLeft, NodeRight)+sum((start + end) / 2 +1, end, node * 2 + 1, NodeLeft, NodeRight);
}
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll ans = 0;
	cin >> N;
	 
	treeNode = vector<ll>(4*N+40,0);

	for (int i = 1; i <= N; i++)
	{
		int x;
		cin >> x;
		ma[i] = x;
	}
	for (int i = 1; i <= N; i++)
	{	
		int y;
		cin >> y;
		re[y] = i;
	}
	for (int i = 1; i <= N; i++) {
		int cur = ma[i];
		int reflect = re[cur];
  
		ans += sum(1, N, 1, reflect + 1, N);
 		update(1, N, 1, reflect, 1);
 	}
	cout << ans;
}
	 

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 도통 모르겠습니다 ㅜ..

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말