[BOJ 2094] 강수량

출처 : https://www.acmicpc.net/problem/2094

 

풀이 : 

 

y, x가 주어졌을때 y~x 사이의 범위에서 최댓값이 x이고 두번째로 큰 값이 y인지 묻는 문제입니다.

y~x 사이의 범위의 최댓값은 세그먼트 트리로 구하면 되고

그거완 별개로 모든 연도의 강수량 정보가 주어지는 것은 아니기 때문에 y와 x의 강수량이 주어졌는지 확인해주셔야합니다.

따라서 3가지의 케이스를 검사해야합니다.

case 1: x년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 x년도의 강수량보다 작은가

case 2: y년도의 강수량이 있을때 y+1 ~ x-1 사이의 최댓값이 y년도의 강수량보다 작은가

case 3: x년도의 강수량이 있고, y년도의 강수량이 있을때 y ~ x 사이의 모든값이 주어져있는가

 

#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;
#define p pair<int, int>
#define f first
#define s second
 
int n, m, b, c, base, seg[1 << 17], x, y, smax, ret;
vector<p> v;
bool xchk, ychk;
 
int search(int idx, int l, int r,int xx,int yy) {
    if (xx > r || yy < l)return 0;
    if (xx <= l && yy >= r)return seg[idx];
    int mid = (l + r + 1) / 2;
    return max(search(idx * 2, l, mid - 1, xx, yy), search(idx * 2 + 1, mid, r, xx, yy));
}
 
int solve() {
    y = lower_bound(v.begin(), v.end(), make_pair(b, 0)) - v.begin();
    x = lower_bound(v.begin(), v.end(), make_pair(c, 0)) - v.begin();
    xchk = x < n&&v[x].f == c;
    ychk = y < n&&v[y].f == b;
    if (xchk&&ychk&&v[x].s > v[y].s)return -1;//false
    smax = search(1, 1, base, lower_bound(v.begin(), v.end(), make_pair(b + 1, 0)) - v.begin() + 1, x);
    if (xchk&&smax >= v[x].s)return -1;
    if (ychk&&smax >= v[y].s)return -1;
    if (xchk && ychk&&x - y == c - b)return 0;//true
    return 1;//maybe
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    base = pow(2, (int)log2(n) + 1);
    for (int i = base; i < base + n; i++) {
        cin >> x >> y;
        v.push_back({ x,y });
        seg[i] = y;
    }
    for (int i = base - 1; i > 0; i--)seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    cin >> m;
    while (m--) {
        cin >> b >> c;
        ret = solve();
        if (ret > 0)cout << "maybe\n";
        else if (!ret)cout << "true\n";
        else cout << "false\n";
    }
}