190205 BOJ 2094번 강수량

브루트 포스, 세그먼트 트리

- 하루 12시간 동안 매달렸던 문제

- 34번째 제출만에 통과

- 문제를 제대로 이해하지 못했고 경우의 수 분류, 구현하는데 있어서 꼼꼼함이 부족했다... 

- 수작업으로 테스트케이스를 막 만들다보니 틀린 부분을 발견할 수 있었다.

- 코드를 너무 더럽게 짰다 ㅜㅜ

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118

#include <iostream> #include <algorithm> #include <map> #define FOR(i,a,b) for(int i = a; i < b; i++) #define endl '\n' #define ll long long #define mp(a,b) make_pair(a,b) #define sws ios::sync_with_stdio(false), cin.tie(NULL) #define MAX 2147000000 #define pii pair<int, int> using namespace std; int N, M, Y, X; pii info[50002]; int val[50002]; int Tree[131071]; int stnode = 65535; bool cmp(pii a, pii b) {     return a.first < b.first; } void update(int a) {     while (a > 0) {         if (a % 2 == 0) a = (a - 1) / 2;         else a /= 2;         int left = a * 2 + 1, right = a * 2 + 2;         Tree[a] = max(Tree[left], Tree[right]);     } } bool query(int st, int ed, int value) {     st = st + stnode;     ed = ed + stnode;     if (Tree[st] >= value) return false;     if (Tree[ed] >= value) return false;     while (st <= ed) {         if (st % 2 == 0) {             if (Tree[st] >= value) return false;         }         if (ed % 2 == 1) {             if (Tree[ed] >= value) return false;         }         if (st == ed) break;         st /= 2;         ed = (ed - 2) / 2;     }     return true; } int main() {     sws;     map<int, int> m;     FOR(i, 0, 131071) Tree[i] = -MAX;     cin >> N;     if (N == 0) return 0;     FOR(i, 0, N) {         cin >> info[i].first >> info[i].second;         val[i] = info[i].second;     }     sort(info, info + N, cmp);     FOR(i, 0, N) {         m[info[i].first] = i;         Tree[i + stnode] = info[i].second;     }     FOR(i, 0, N) update(i + stnode);     cin >> M;     while (M--) {         cin >> Y >> X;         if (m.count(X) == 0) {             if (m.count(Y) == 0) {                 cout << "maybe\n";                 continue;             }             X = info[upper_bound(info, info + N, mp(X, 0), cmp) - info - 1].first;             if (m.at(X) == m.at(Y)) {                 cout << "maybe\n";                 continue;             }             bool ans = query(m.at(Y) + 1, m.at(X), info[m.at(Y)].second);             if (ans) cout << "maybe\n";             else cout << "false\n";             continue;         }         if (m.count(Y) == 0) {             if (Y < info[0].first) {                 if (X == info[0].first) {                     cout << "maybe\n";                     continue;                 }                 bool ans = query(0, m.at(X) - 1, info[m.at(X)].second);                 if (ans) cout << "maybe\n";                 else     cout << "false\n";                 continue;             }             Y = info[lower_bound(info, info + N, mp(Y, 0), cmp) - info - 1].first;             if (m.at(X) - m.at(Y) == 1) {                 cout << "maybe\n";                 continue;             }             bool ans = query(m.at(Y) + 1, m.at(X) - 1, info[m.at(X)].second);             if (ans)    cout << "maybe\n";             else cout << "false\n";             continue;         }         if (m.at(X) - m.at(Y) == 1) {             if (info[m.at(X)].second <= info[m.at(Y)].second) {                 if (X - Y == m.at(X) - m.at(Y))cout << "true\n";                 else cout << "maybe\n";             }             else cout << "false\n";             continue;         }         if (info[m.at(Y)].second < info[m.at(X)].second) {             cout << "false\n";             continue;         }         bool ans = query(m.at(Y) + 1, m.at(X) - 1, info[m.at(X)].second);         if (ans && X - Y != m.at(X) - m.at(Y)) cout << "maybe\n";         else if (ans) cout << "true\n";         else cout << "false\n";     } } Colored by Color Scripter

cs