BOJ1637 날카로운 눈 질문드립니다

[zezeg2]

import java.io.*;
import java.util.*;

public class BOJ1637 {
    static StringBuilder sb = new StringBuilder();
    static FastReader scan = new FastReader();

    static int N, maxint, ans, total;
    static int[] A,B,C;

    static void input() {
        N = scan.nextInt();
        maxint = Integer.MIN_VALUE;
        A = new int[N];
        B = new int[N];
        C = new int[N];
        for (int i = 0; i < N; i++){
            A[i] = scan.nextInt();
            B[i] = scan.nextInt();
            C[i] = scan.nextInt();
            maxint = Math.max(maxint,B[i]);
        }
    }

    static void pro() {
        int left = 1;
        int right = maxint;
        boolean noodd = true;
        while (right >= left) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0; i < N; i++) {
                if(A[i] > mid) continue;
                if (B[i] >= mid) cnt += (mid - A[i]) / C[i];
                else cnt += (B[i] - A[i]) / C[i] + 1;

            }
            if (cnt % 2 == 0) {
                ans = mid;
                left = mid + 1;
            }
            
            else {
                right = mid - 1;
                noodd = false;
            }
        }

        if (noodd) sb.append("NOTHING");
        else{
            for (int i = 0; i < N; i++) {
                if ((ans <= B[i] && ans >= A[i]) && ((ans - A[i]) % C[i] == 0)) total++;
            }
            sb.append(ans).append(' ').append(total);
        }
    }
    
    public static void main(String[] args) {
        input();
        pro();
        System.out.println(sb);
    }


    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

우선 컴파일 해서 테스트 케이스 정답과 일치하는지 확인하고 제출 하였습니다. 그런데 시간초과로 실패하게 되었는데, 제가 생각한 시간복잡도는 홀수인 정수를 찾는 과정에서 이분탐색으로 Nlog(N), 그리고 정수의 갯수를 구하는 과정에서 N으로 계산된다고 생각했는데 제가 잘못 판단하고 있는 부분이 있을까요?, 솔루션으로 올려주신 파일과도 논리적으로 크게 다를게 없다고 판단하는데... 문제점 지적해주시면 감사하겠습니다

[rhs0266]

이건 문제를 꼼꼼히 읽어도 충분히 하실 수 있는 실수인 것 같습니다. 저도 종종 실수해서요.

maxint 가 21억 4748만 3647 이라고 하겠습니다. 그러면 mid 계산 시에 (left + right) 가 int 범위를 벗어나면서 mid 계산이 의도대로 되지 않을 것입니다.

또한 cnt 에 계산될 값 또한 엄청 커질 수 있는데, 왜 그런 지 한 번 직접 확인해보시는 것이 좋아보여요.