글 읽기 - 시간초과에 걸리는데 좋은 방법 없을까요?

(追記) (追記ここまで)

시간초과에 걸리는데 좋은 방법 없을까요?

11012번 - Egg

powerlsj7 2년 전 0

n*m 반복문이 범위가 커지면 당연히 시간초과 걸릴 것 같은데 줄일 방법이 떠오르지 않네요.

로직은 정답이 나오는 것 같은데..

using System.IO;
using System.Text;
using System;
using System.Collections.Generic;
class Programs
{
 static StreamReader sr = new StreamReader(Console.OpenStandardInput(), Encoding.Default);
 static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput(), Encoding.Default);
 class XY : IComparable
 {
 public int x, y;
 public XY(int x, int y)
 {
 this.x = x;
 this.y = y;
 }
 public int CompareTo(object obj)
 {
 XY a = this;
 XY b = (XY)obj;
 if (a.x.Equals(b.x))
 {
 return a.y.CompareTo(b.y);
 }
 return a.x.CompareTo(b.x);
 }
 }
 class XYXY
 {
 public int x, x2, y, y2;
 public XYXY(int x, int x2, int y, int y2)
 {
 this.x = x;
 this.y = y;
 this.x2 = x2;
 this.y2 = y2;
 }
 }
 static int[] tree;//변수가 두개인거지 ᅳᅳ;;
 static List<XYXY> xyxy = new List<XYXY>();
 static List<XY> xy = new List<XY>();
 static void SegmentTreeUpdate(int s, int e, int y, int value, int root)
 {
 if (s > y || e < y)
 {
 return;
 }
 if (s == e)
 {
 tree[root] = value;
 return;
 }
 int mid = (s + e) / 2;
 int left = root * 2 + 1;
 int right = root * 2 + 2;
 SegmentTreeUpdate(s, mid, y, value, left);
 SegmentTreeUpdate(mid + 1, e, y, value, right);
 tree[root] = tree[left] + tree[right];
 }
 static int SegmentTreeSum(int s, int e, int l, int r, int root)//일단 테스트
 {
 if (s > r || e < l)
 {
 return 0;
 }
 if (l <= s && e <= r)
 {
 return tree[root];
 }
 int mid = (s + e) / 2;
 int left = root * 2 + 1;
 int right = root * 2 + 2;
 return SegmentTreeSum(s, mid, l, r, left) + SegmentTreeSum(mid + 1, e, l, r, right);
 }
 static void Main(String[] args)
 {
 int t = int.Parse(sr.ReadLine());
 //y를 반복문으로 접근해서 범위 합을 구하고 x범위는 세그먼트트리로
 //알 것 같음...
 //x축으로 정렬한뒤 점을 일단 찍는다 
 //찍은 점을 세그먼트트리에 업데이트해주고
 //m번 만큼 반복문으로 해당x가 범위에 포함되는지 확인한 후 
 //y~y범위에 좌표가 몇개 있는지 확인
 //개수를 다 더한뒤 출력
 //좌표압축 따로 필요없음. 1차원 세그먼트트리로 가능함
 for (int i = 0; i < t; i++)
 {
 string[] str = sr.ReadLine().Split();
 int n = int.Parse(str[0]);
 int m = int.Parse(str[1]);
 tree = new int[100000 * 4];
 xy.Clear();//x축 정렬은 해야하기때문에 필요.
 xyxy.Clear();
 for (int j = 0; j < n; j++)//xy좌표 계란을 던지는 사람이 있는 곳
 {
 string[] s = sr.ReadLine().Split();//좌표가 중복되면...어...
 int x = int.Parse(s[0]);
 int y = int.Parse(s[1]);
 //그러면 xy는 따로 저장해주고
 xy.Add(new XY(x, y));
 }
 xy.Sort();//정렬완료.
 int answer = 0;
 int size = 0;
 for (int j = 0; j < m; j++)//퍼레이드 지역범위 해당 범위안에 계란을 던지는 사람이 있으면 포함
 {
 string[] s = sr.ReadLine().Split();
 int x1 = int.Parse(s[0]);
 int x2 = int.Parse(s[1]);
 int y1 = int.Parse(s[2]);
 int y2 = int.Parse(s[3]);
 size = Math.Max(y1, Math.Max(y2, size));
 xyxy.Add(new XYXY(x1, x2, y1, y2));
 }
 xyxy.Sort((a, b) => {
 if (a.x.Equals(b.x))
 {
 return a.x2.CompareTo(b.x2);
 }
 return a.x.CompareTo(b.x);
 });
 for (int j = 0; j < n; j++)
 {
 //좌표를 갱신해줌
 SegmentTreeUpdate(0, size, xy[j].y, 1, 0);
 for (int a = 0; a < m; a++)
 {
 if (xyxy[a].x <= xy[j].x && xy[j].x <= xyxy[a].x2)//왜 안나옴?;;
 {
 answer += SegmentTreeSum(0, size, xyxy[a].y, xyxy[a].y2, 0);
 }
 else if(xy[j].x<xyxy[a].x)
 {
 //아예 범위 밖은 종료
 break;
 }
 }
 SegmentTreeUpdate(0, size, xy[j].y, 0, 0);
 }
 sw.WriteLine(answer);
 }
 sw.Dispose();
 }
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

시간초과에 걸리는데 좋은 방법 없을까요?

powerlsj7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말