글 읽기 - 라운드로빈 문제 어디 부분이 틀린건가요?

kkw564 7년 전 0

10000

1000000000 1000000000 ...

10000개모두 1000000000으로 해서 돌리면 값이 어중이떠중이로 나오네요

일반 값들은 모두 통과하는데

어디서 잘못된거죠..?

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

typedef struct _ROUND_
{
	int idx;
	ll time;
	ll ans;
}ROUND;

ROUND robin[100001];
ll sum;

bool comp(const ROUND &a, const ROUND &b)
{
	return a.time < b.time;
}


ll init(vector<ll> &tree, int node, int start, int end)
{
	if (start == end)
		return tree[node] = robin[start].time;

	int mid = (start + end) / 2;

	return init(tree, node * 2, start, mid) + init(tree, node * 2 + 1, mid + 1, end);
}

void update(vector<ll> &tree, int node, int start, int end, int index, ll diff)
{
	if (!(start <= index && index <= end))
		return;

	tree[node] += diff;

	if (start != end)
	{
		int mid = (start + end) / 2;

		update(tree, node * 2, start, mid, index, diff);
		update(tree, node * 2 + 1, mid + 1, end, index, diff);
	}
}

ll query(vector<ll> &tree, int node, int start, int end, int left, int right)
{
	if (right < start || left > end)
		return 0;

	if (left <= start && end <= right)
		return tree[node];

	int mid = (start + end) / 2;
	
	return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2 + 1, mid + 1, end, left, right);
}

int main()
{
	int n;

	scanf("%d", &n);


	int h = (int)ceil(log2(n));
	int tree_size = (1 << (1 + h));

	vector<ll> tree(tree_size);

	for (int i = 0; i < n; i++)
	{
		ll val;
		scanf("%lld", &val);

		robin[i].idx = i;
		robin[i].time = val;
		update(tree, 1, 0, n - 1, i, 1);
	}

	sort(robin, robin + n, comp);
	
	for (int i = 0; i < n; i++)
	{
		int idx = robin[i].idx;
		ll time = robin[i].time;
		robin[idx].ans = query(tree, 1, 0, n - 1, 0, idx) * time + query(tree, 1, 0, n - 1, idx + 1, n - 1)* (time - 1) + sum;
	
		update(tree, 1, 0, n - 1, idx, -1);
		sum += time;
	}
	
	for (int i = 0; i < n; i++)
		printf("%lld\n", robin[i].ans);

	return 0;
}

smu201111192 7년 전 0

시간이 같은경우에 대해서도 비교를 해주셔야 될 거 같습니다.

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

문제

문제

출처

ICPC

라운드로빈 문제 어디 부분이 틀린건가요?

kkw564 7년 전 0

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말