글 읽기 - 아무리생각해도 어디가 잘못된건지 모르겠습니다 ㅜ.

isvara 4년 전 0

코드에 잘못된점이나 반례제시해주실 고수분 계신가요 ??

#include<iostream>
#include<algorithm>
#include<string>
#include<set>
#include<utility>
#include<queue>
#include<vector>
#include<math.h>
#include<map>
#include<cstring>
using namespace std;
typedef long long ll;
const int max_node = 100001;

int N;
int a[max_node];
ll hi[max_node];
ll lo[max_node];
vector<int>tree;
 
void update(int left, int right, int node, int target)
{
	if (target < left || right < target)
		return;
	
	tree[node] += 1;

	if (left != right) {
		int mid = (left + right) / 2;
		update(left, mid, 2 * node, target);
		update(mid + 1, right, 2 * node + 1, target);
	}
}
int query(int left, int right, int node, int NodeLeft, int NodeRight)
{
	if (NodeRight < left || right < NodeLeft)
		return 0;
	if (NodeLeft <= left && right <= NodeRight)
		return tree[node];
	int mid = (left + right) / 2;
	return query(left, mid, node * 2, NodeLeft, NodeRight)+query(mid+1,right,node*2+1,NodeLeft,NodeRight);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> a[i];
	tree.resize(4 * N);
	
	for (int i = 0; i < N; i++)
	{
		hi[i] = query(0, N - 1, 1, a[i], N-1);
		update(0, N - 1, 1, a[i]-1);
	}
	tree = vector<int>(N * 4);
	for (int i = 0; i < N; i++)
	{
		lo[i] = query(0, N - 1, 1, 0, a[i]-2);
		update(0, N - 1, 1, a[i]-1);
	}
	ll ans = 0;

	for (int i = 0; i < N; i++)
		ans += lo[i] * hi[i];
	
	cout << ans;
}

yukino 4년 전 0

작은 수를 찾을 때는 오른쪽을 봐야 되서, 59번 줄 for문을 반대로 하면 될거 같아요.

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

문제

문제

출처

ICPC

아무리생각해도 어디가 잘못된건지 모르겠습니다 ㅜ.

isvara 4년 전 0

yukino 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말