글 읽기 - 구간 합 구하기 3 - 원인을 모르겠네요...

hultul 6년 전 0

2차원 합을 저장하는 펜윅 트리로 작성했습니다.
샘플 통과하고, 혹시나 로컬 테스트로 랜덤 숫자 만들어 O(n²) brute force 계산과 비교해도 동일하게 나오는데...사이트에 제출하면 틀렸다네요.

#include <stdio.h>

void
modify(long long **FWK, int N, int X, int Y, long long V)
{
    int x;
    int y = Y;
    while (y <= N) {
        x = X;
        while (x <= N) {
            FWK[y][x] += V;
            x += x & -x;
        }
        y += y & -y;
    }
}

long long
sum(long long **FWK, int X, int Y)
{
    int x;
    int y = Y;
    long long s = 0;
    while (y > 0) {
        x = X;
        while (x > 0) {
            s += FWK[y][x];
            x -= x & -x;
        }
        y -= y & -y;
    }

    return s;
}

long long
sum_range(long long **FWK, int X1, int Y1, int X2, int Y2)
{
    return sum(FWK, X2, Y2) - sum(FWK, X1 - 1, Y2) - sum(FWK, X2, Y1 - 1) + sum(FWK, X1 - 1, Y1 - 1);
}
    
long long
sum_bf(long long **A, int X1, int Y1, int X2, int Y2)
{
    long long s = 0;
    for (int y = Y1; y <= Y2; y++) {
        for (int x = X1; x <= X2; x++) {
            s += A[y][x];
        }
    }
    return s;
}

int
main()
{
    int N, M;
    long long **A, **FWK;

    scanf("%d %d", &N, &M);
    FWK = new long long*[N + 1];
    A = new long long*[N + 1];

    for (int i = 1; i <= N; i++) {
        A[i] = new long long[N + 1]();
        FWK[i] = new long long[N + 1]();
    }
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            long long v;
            scanf("%lld", &v);
            A[i][j] = v;
            modify(FWK, N, j, i, v);
        }
    }

    for (int i = 0; i < M; i++) {
        int w, a, b, c, d;
        scanf("%d", &w);
        
        if (w == 0) {
            scanf("%d %d %d", &a, &b, &c);
            if (a >= 1 && a <= N && b >= 1 && b <= N) {
                modify(FWK, N, a, b, (long long)c - A[b][a]);
                A[b][a] = (long long)c;
            }
        } else if (w == 1) {
            long long s = 0;
            int x1, x2, y1, y2;
            
            scanf("%d %d %d %d", &a, &b, &c, &d);
            
            x1 = (a <= c) ? a : c;
            x2 = (a <= c) ? c : a;
            y1 = (b <= d) ? b : d;
            y2 = (b <= d) ? d : b;

            if (x1 > N || x2 < 1 || y1 > N || y2 < 1)  {
                s = 0;
            } else {
                x1 = (x1 < 1) ? 1 : x1;
                y1 = (y1 < 1) ? 1 : y1;
                s = sum_range(FWK, x1, y1, x2, y2);
            }
            printf("%lld\n", s);
        }
    }    
}

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

문제

문제

출처

ICPC

구간 합 구하기 3 - 원인을 모르겠네요...

hultul 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말