글 읽기 - (java)틀리다고 뜨네요. 뭐가 문제일까요?

reperdof 1년 전 0

스위핑+세그먼트 트리를 사용하고 있습니다.

y축에 대한 세그먼트 트리를 만들고 0~100000까지 x축에 대해 스위핑하며 home이 parade area와 겹치는 횟수를 더하는 식으로 구현하였습니다.

예제는 맞는데 채점 도중 틀렸습니다가 나오네요;; 제가 미처 생각하지 못하는 부분이 있는 걸까요?

무엇이 문제인지 알려주신다면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.math.*;
import java.text.DecimalFormat;

public class Main {
	
	static int[] tr;
	static final int max = 100001;
	
	public static void main(String[] args) throws IOException {
		BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter ww = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(rr.readLine());
		for (int z = 0; z < T; z++) {
			String[] s = rr.readLine().split(" ");
			int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
			
			ArrayList<int[]>[][] area = new ArrayList[max][2]; // parade area 저장
			ArrayList<Integer>[] egg = new ArrayList[max]; // home 위치 저장
			for (int i = 0; i < max; i++) {
				area[i][0] = new ArrayList<>();
				area[i][1] = new ArrayList<>();
				egg[i] = new ArrayList<>();
			} // area, egg 배열 초기화
			tr = new int[4*max]; // 세그먼트 트리 초기화
			
			for (int i = 0; i < n; i++) {
				s = rr.readLine().split(" ");
				int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]);
				egg[x].add(y);
			} // home 위치 입력
			for (int i = 0; i < m; i++) {
				s = rr.readLine().split(" ");
				int x1 = Integer.parseInt(s[0]), x2 = Integer.parseInt(s[1]);
				int y1 = Integer.parseInt(s[2]), y2 = Integer.parseInt(s[3]);
				int[] c = {y1, y2};
				area[x1][0].add(c); area[x2][1].add(c);
			} // parade area 입력
			
			long sum = 0;
			for (int i = 0; i < max; i++) { // 0 ~ max-1의 x 좌표
				for (int[] c : area[i][0]) {
					ad(1, 0, max, c[0], c[1], 1); // parade area를 segment tree에 추가
				}
				for (int c : egg[i]) {
					sum += ch(1, 0, max, c); // 각 home에 대하여 parade area와 겹치는 수를 segment tree에서 찾는다
				}
				for (int[] c : area[i][1]) {
					ad(1, 0, max, c[0], c[1], -1); // parade area를 segment tree에서 제거
				}
			}
			ww.write(Long.toString(sum) + "\n"); // 출력
		}
		ww.flush();
		ww.close();
	}
	
	static void ad(int n, int i, int j, int a, int b, int s) { // 전체 i~j의 구간에서  a~b의 구간에 s를 더해준다
		if (i == a && j == b) { // i~j와 a~b가 동일할 경우 바로 더한다
			tr[n] += s;
			return;
		}
		int mid = (i+j)/2;
		if (mid >= b) ad(2*n, i, mid, a, b, s);
		else if (mid < a) ad(2*n+1, mid+1, j, a, b, s);
		else {
			ad(2*n, i, mid, a, mid, s);
			ad(2*n+1, mid+1, j, mid+1, j, s);
		}
	}
	
	static long ch(int n, int i, int j, int a) { // i~j의 구간에서 위치 a에 해당하는 값을 출력한다
		if (i == j) {
			return tr[n];
		}
		int mid = (i+j)/2;
		long sum = tr[n];
		if (mid >= a) sum += ch(2*n, i, mid, a);
		else sum += ch(2*n+1, mid+1, j, a);
		return sum;
	}
}

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

문제

문제

출처

ICPC

(java)틀리다고 뜨네요. 뭐가 문제일까요?

reperdof 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말