글 읽기 - 이 코드가 어디가 틀린지 모르겠습니다.

haz102 7년 전 1

제가 보기엔 큰 문제 없는듯 한데요,

어디가 틀린지 모르겠습니다.ㅜㅜ

고수님들 부탁드려요

// https://www.acmicpc.net/problem/12016
 
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int N;
long long tree[200010] = { 0, };
 
void update(int idx, int diff)
{
    for (int i = idx; i <= N; i += (i&-i))
    {
        tree[i] += diff;
    }
}
 
long long sum(int idx)
{
    int ans = 0;
 
    for (int i = idx; i > 0; i -= (i&-i))
    {
        ans += tree[i];
    }
 
    return ans;
}
 
long long sum(int from, int to)
{
    if (to > from)
    {
        return 0;
    }
 
    return sum(to) - sum(from - 1);
}
 
class Data
{
public:
    int order;
    int value;
 
    int Compare(Data* d)
    {
        if (value == d->value)
        {
            return d->order - order;
        }
 
        return d->value - value;
    };
};
 
Data data[100010];
inline void swap(Data* l, Data* r)
{
    int t = l->order;
    l->order = r->order;
    r->order = t;
 
    t = l->value;
    l->value = r->value;
    r->value = t;
}
 
void qsort(int left, int right)
{
    if (left < right)
    {
        int l = left;
        int r = right;
        Data p;
        p.order = data[left].order;
        p.value = data[left].value;
 
        while (l < r)
        {
            while (l < r && p.Compare(&data[r]) > 0)
            {
                r--;
            }
 
            while (l < r && p.Compare(&data[l]) <= 0)
            {
                l++;
            }
 
            swap(&data[l], &data[r]);
        }
 
        data[left].order = data[l].order;
        data[left].value = data[l].value;
 
        data[l].order = p.order;
        data[l].value = p.value;
 
        qsort(left, l - 1);
        qsort(l + 1, right);
    }
}
 
long long ans[200010] = { 0, };
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &data[i].value);
        data[i].order = i;
        update(i, 1);
    }
 
    qsort(1, N);
 
    int remain = N;
    int last = 0;
    long long total = 0;
 
    for (int i = 1; i <= N; i++)
    {
        int pos = data[i].order;
        total += (long long)(data[i].value - last) * remain;
        remain--;
 
        last = data[i].value;
        ans[pos] = total - sum(pos + 1, N);
        update(pos, -1);
    }
 
    for (int i = 1; i <= N; i++)
    {
        printf("%lld\n", ans[i]);
    }
 
    return 0;
}

zlzmsrhak 7년 전 0

33번째 줄에 부등호 방향이 반대인 거 같습니다

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

문제

문제

출처

ICPC

이 코드가 어디가 틀린지 모르겠습니다.

haz102 7년 전 1

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말