글 읽기 - 틀린 예제가 뭐가 있을까요?

dydsj0920 5년 전 0

Fenwick트리를 써서 작성했는데
예제는 맞지만 답이 틀리다고 나오네요..
어디가 잘못됐을까요?

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void update(vector<int>&tree, int idx, int diff) {
    for (int i = idx; i < tree.size(); i += i & -i) {
        tree[i] += diff;
    }
}

int sum(vector<int>&tree, int idx) {
    int ans = 0;
    for (int i = idx; i > 0; i -= i & -i) {
        ans += tree[i];
    }
    return ans;
}

int sum(vector<int> &tree, int l, int r) {
    return sum(tree, r) - sum(tree, l - 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n + 1);
    vector<int> tree1(n + 1);
    vector<int> tree2(n + 1);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        update(tree1, a[i], 1);
        update(tree2, a[i], sum(tree1, a[i] + 1, n));
        ans += (long long)sum(tree2, a[i] + 1, n);
    }
    printf("%lld\n", ans);

    return 0;
}

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

문제

문제

출처

ICPC

틀린 예제가 뭐가 있을까요?

dydsj0920 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말