글 읽기 - 예제는 맞는데,, 왜 틀리는 지 도저히 모르겠습니다.

3juhwan 2년 전 0

cpp 공부한지 얼마 안되서, 오버프로우나 자료형 관련 경험이 없습니다..

이론적으론 아는데, 문제를 풀려니까 왜 안되는지 모르겠습니다.

도와주시면 감사하겠습니다 !!

+ 추가: 똑같은 코드를 pypy로 제출했을 때, 정답이 뜹니다. 오버플로우 문제 같은데 도움 부탁드립니다🙏🙏

#include <iostream>
#include <algorithm>
#include <string.h>
#include <utility>

using namespace std;

const int MOD = 1000000007;
const int MAX = 200001;
pair<long long, int> tree[MAX*4];
int arr[MAX];


pair<long long, int> sum(int left, int right, int node, int start, int end) {
    if (end < left || start > right)
        return make_pair(0, 0);
    if (left <= start && end <= right)
        return tree[node];
    int mid = (start+end)/2;
    pair<long long, int> a = sum(left, right, node*2, start, mid);
    pair<long long, int> b = sum(left, right, node*2+1, mid+1, end);
    return tree[node] = make_pair((a.first+b.first), a.second+b.second);
}


pair<long long, int> modify(int idx, int node, int start, int end) {
    if (idx < start || idx > end)
        return tree[node];
    if (start == end) {
        arr[start] += 1;
        return tree[node] = make_pair(idx*arr[start], arr[start]);
    }
    int mid = (start+end)/2;
    pair<long long, int> a = modify(idx, node*2, start, mid);
    pair<long long, int> b = modify(idx, node*2+1, mid+1, end);
    return tree[node] = make_pair((a.first+b.first), a.second+b.second);
}


int main() {    
    memset(arr, 0, sizeof(arr));
    for (int i=0; i < MAX*4; i++) {
        tree[i].first = 0;
        tree[i].second = 0;
    }

    int n, x;
    pair<long long, int> a, b;
    long long answer=1;

    scanf("%d", &n);
    scanf("%d", &x);
    modify(x, 1, 0, MAX);
  
    for (int i=0; i < n-1; i++) {
        scanf("%d", &x);
        a = sum(0, x-1, 1, 0, MAX);
        b = sum(x+1, MAX, 1, 0, MAX);
        answer = (answer*(x*a.second-a.first+b.first-x*b.second))%MOD;
        modify(x, 1, 0, MAX);
    }  
    printf("%lld", answer);
}

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

문제

문제

출처

ICPC

예제는 맞는데,, 왜 틀리는 지 도저히 모르겠습니다.

3juhwan 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말