글 읽기 - 이거 정말 반례가 뭔지 모르겠습니다 ㅠㅠ 도와주세요 ㅠㅠ

nodap 5년 전 0

우선 두개의 년도수가 명확히 데이터에존재하는경우, 연속적인 데이터의 범위일때 true, maybe를 따질수 있다고 생각했습니다. 만약 애초에 2번조건에 의해서 강수량이 만족되지 못한다면 그 경우는 false로 분류를 미리 했습니다.

혹은 두개의 년도수에 대해서 정확히 알지 못할경우,

총 3가지로 분류를 했습니다.

Y는 아는데 X를 모르는 경우 -> X보다 바로 작은 데이터 범위를 찾아서 Y바로 다음정점부터 X바로 작은 데이터 범위를 비교하였습니다
X는 아는데 Y를 모르는 경우 -> Y보다 바로 큰 데이터 범위부터 X 바로 이전정점까지의 중간값을 X와 비교하였고, 만약 중간값이 더크면 불가능
둘다 모르는 경우 -> 둘사이에 유효한 범위(데이터가 존재하는)내에서 1e9값만 나오지않는다면 maybe, 나오면 false라고 했습니다

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;
#define INF 1000000000
typedef pair<int, int> P;
typedef pair<pair<int, int>, int> PP;
typedef pair<int, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
vector<int> seg;
int h = 1;
int n, m;
map<int, int> check, check2, check3;
void update(int index, int value) {
	index += h - 1;
	seg[index] = value;
	while (index > 1) {
		index /= 2;
		seg[index] = max(seg[index * 2], seg[index * 2 + 1]);
	}
}
int query(int nodenum, int left, int right, int nodeleft, int noderight) {
	if (left > noderight || right < nodeleft) return 0;
	else if (left <= nodeleft && noderight <= right) return seg[nodenum];
	int mid = (nodeleft + noderight) / 2;
	return max(query(nodenum * 2, left, right, nodeleft, mid), query(nodenum * 2 + 1, left, right, mid + 1, noderight));
}
int main() {
	vector<int> v;
	scanf("%d", &n);
	int here = 1;
	while (h < n) h *= 2;
	seg.resize(h * 2);
	for (int i = 1; i <= n; i++) {
		int first, cost;
		scanf("%d%d", &first, &cost);
		if (check.count(first) == 0) {
			check[first] = here; // 년도수에 매칭되는 정점
			check2[first] = cost; // 정점의 강수량
			check3[here] = first; // 정점에 매칭되는 원래의 년도수
			v.push_back(first);
		}
		update(here, cost);
		here++;
	}
	scanf("%d", &m);
	here--;
	vector<int>::iterator it, it2;
	for (int i = 1; i <= m; i++) {
		int left, right;
		scanf("%d%d", &left, &right);
		if (check.count(left) == 0 || check.count(right) == 0) {
			if (check.count(left) != 0 && check.count(right) == 0) { // Y는 알고  X를 모를때(이게문제)
				it = lower_bound(v.begin(), v.end(), right);
				it--;
				if (check[left] == check[*it]) {
					printf("maybe\n");
					continue;
				}
				int Max = query(1, check[left] + 1, check[*it], 1, h);
				if (Max >= check2[left]) printf("false\n");
				else printf("maybe\n");
			}
			else if (check.count(right) != 0 && check.count(left) == 0) { //X는 알고 Y를 모를때
				it = lower_bound(v.begin(), v.end(), left);
				if (check[*it] == check[right]) {
					printf("maybe\n");
					continue;
				}
				int Max = query(1, check[*it], check[right] - 1, 1, h);
				if (Max >= check2[right]) printf("false\n");
				else printf("maybe\n");
			}
			else if (check.count(left) == 0 && check.count(right) == 0) { // 둘다 모를때
				it = lower_bound(v.begin(), v.end(), left);
				it2 = lower_bound(v.begin(), v.end(), right);
				if (it == v.end() || it2 == v.begin()) {
					printf("maybe\n");
					continue;
				}
				if (it2 == v.end()) it2--;
				int Max = query(1, check[*it], check[*it2], 1, h);
				if (Max == 1e9) printf("false\n");
				else printf("maybe\n");
			}
			continue;
		}
		if (check2[left] < check2[right]) printf("false\n");
		else if (check[right] - check[left] > 1) {
			// 연속적인 경우 모든 경우의 년도수가 강수량으로 체크가 되어있을때
			int Max = query(1, check[left] + 1, check[right] - 1, 1, h);
			if (Max >= check2[right]) printf("false\n"); //그냥 클때(Max가 Z년도가 X년도보다 같거나 클경우)
			else {
				if (check[right] - check[left] == abs(check3[check[right]] - check3[check[left]])) { // 연속적인 년도의 경우일때
					printf("true\n");
				}
				else printf("maybe\n"); // 아닐때
			}
		}
		else if (check[right] - check[left] == 1) { // 그냥 바로 인접하는경우
			if (check2[left] < check2[right]) printf("false\n");
			else printf("true\n");
		}
	}
	return 0;
}

fashion 5년 전 1

2 40

4 10

2 4

maybe로 나와야 하는데 true로 나오네요

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

문제

문제

출처

ICPC

이거 정말 반례가 뭔지 모르겠습니다 ㅠㅠ 도와주세요 ㅠㅠ

nodap 5년 전 0

fashion 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말