글 읽기 - 5%에서 계속 틀립니다. 조언 부탁드립니다.

mnme3737 1년 전 0

질문게시판을 정독하여 long 자료형 변환(segmentTree 및 diff 변수 등), x~y번째 값 까지 구간합을 구할 때 x와 y의 크기 비교, 등 주요 문제사항은 다 수정한 것 같습니다. 블로그 답안을 찾아보면서 코드를 비교해보기도 했는데 정확히 어떤 부분이 틀린건지 2시간 내내 들여다봐도 찾을 수가 없습니다ㅠ 부디 도와주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int [] arr = null;
    static long [] segmentTree = null;
    
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int N = Integer.parseInt(st.nextToken()); //원소의 개수
        int Q = Integer.parseInt(st.nextToken()); //질문의 개수

        arr = new int[N+1];
        segmentTree = new long [N*4];

        //데이터 입력받기
        st = new StringTokenizer(bf.readLine());
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //SegmentTree 생성
        makeSegmentTree(1, 1, N);

        for(int i=0; i<Q; i++){
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            long diff = val-arr[idx];
            
            //a부터 b까지(min과 max 사이) sum 구하기
            sb.append(sum(1, 1, N, Math.min(a,b),Math.max(a,b))).append("\n");
            //idx번째 원소를 val로 교체(diff만큼 값 추가)해주기
            updateSegment(1, 1, N, idx, diff);
            arr[idx] = val;

        }

        System.out.println(sb);
    }

    //SegmentTree 생성 함수
    static long makeSegmentTree(int node, int start, int end){
        if(start == end) return segmentTree[node] = arr[start];

        int mid = (start+end)/2;
        long leftResult = makeSegmentTree(node*2, start, mid);
        long rightResult = makeSegmentTree(node*2+1, mid+1,end);
        segmentTree[node] = leftResult+rightResult;

        return segmentTree[node];
    }

    //구간합 구하기 함수
    static long sum(int node, int start, int end, int left, int right){
        if(left>end || right<start) return 0;
        if(left<=start && end<=right) return segmentTree[node];

        int mid = (start+end)/2;
        long leftResult = sum(node*2, start, mid, left, right);
        long rightResult = sum(node*2+1, mid+1, end, left, right);

        return leftResult+rightResult;
    }
    
    //SegmentTree Update 함수
    static void updateSegment(int node, int start, int end, int idx, long diff){

        if(idx<start || end<idx) return;

        segmentTree[node] += diff;

        if(start != end){
            int mid = (start+end)/2;
            updateSegment(node*2, start, mid, idx, diff);
            updateSegment(node*2+1, mid+1, end, idx, diff);
        }
    }
}

djm03178 1년 전 0

37번째 줄 val-arr[idx]에서 오버플로가 발생할 수 있습니다.

mnme3737 1년 전 0

와 long으로 받아서 괜찮을 줄 알았는데 아니었네요.. arr[idx] 를 long으로 캐스팅했더니 맞았습니다. 코드 어디 틀렸는지만 주구장창 들여다봤는데.. 감사합니다..!!!

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

문제

문제

출처

ICPC

5%에서 계속 틀립니다. 조언 부탁드립니다.

mnme3737 1년 전 0

djm03178 1년 전 0

mnme3737 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말