글 읽기 - 61%에서 틀렸습니다가 뜹니다

kja9294 4년 전 0

평방 분할 연습할겸 시도해봤는데 도저히 문제점을 못 찾겠습니다.ㅜㅜ 에초에 이 문제는 세그먼트로만 풀 수 있는 건가요??

#include<iostream>
#include<cmath>
#define MAX 1234567890
using namespace std;

int arr[100001];
int sqd[1000][3]; //0,은 최소, 1은 최대, 2는 해당 쿼리 끝나는 부분+1

pair<int,int> calculate(int start,int end) {
	int min = MAX;
	int max = 0;
	for (start; start < end; start++) {
		if (min > arr[start]) min = arr[start];
		if (max < arr[start]) max = arr[start];
	}
	return make_pair(min, max);
}

int main() {
	int n, m;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int s = (int)sqrt(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	int end =0;
	for (int i = 0; i <s; i++) end += s, sqd[i][2] = end;
	sqd[s][2] = n;

	int j=0;
	int i = 0;
	int max, min;
	for (i; i <= s; i++) { //각 쿼리 최대 최소 계산
		min = MAX;
		max = 0;
		for (j; j < sqd[i][2]; j++) {
			if (min > arr[j]) min = arr[j];
			if (max < arr[j]) max = arr[j];
		}
		sqd[i][0] = min;
		sqd[i][1] = max;
	}

	int a, b;
	pair<int, int> left;
	pair<int, int> right;
	for (i = 0; i < m; i++) {
		cin >> a >> b;
		int l = (--a) / s;
		int r = (--b) / s;
		if (l == r) { //한 쿼리만 범위인 경우
			left = calculate(a, b+1);
			min = left.first;
			max = left.second;
		}
		else {
			left = calculate(a, sqd[l][2]);
			right = calculate(sqd[r-1][2], b + 1);
			if (left.first < right.first) min = left.first;
			else min = right.first;
			if (left.second > right.second) max = left.second;
			else max = right.second;
			for (j = l + 1; j <r; j++) { //사이드 제외 후 나머지 비교
				if (sqd[j][0] < min) min = sqd[j][0];
				if (sqd[j][1] > max) max = sqd[j][1];
			}
		}
		cout << min << " " << max << '\n';
	}
}

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

문제

문제

출처

ICPC

61%에서 틀렸습니다가 뜹니다

kja9294 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말