글 읽기 - 세그트리로 segmentation fault가 발생하는 이유를 도저히 모르겠어요

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

세그트리로 segmentation fault가 발생하는 이유를 도저히 모르겠어요

1202번 - 보석 도둑

parkgunwon1 1년 전 0

0 ~ n - 1까지 구간별 최대를 저장해 두고 upper_bound로 현재 가방에 들어갈수있는 가장 큰 인덱스를 구하여 구간 최대의 값을 빠르게 구한뒤 최대값을 구한 인덱스에 값을 -1, -1로 없데이트 하여 추후 이구간이 골라졌을경우 무시되도록 코드를 작성하였는데

어디에서 segfault가 발생할 수 있는것인가요? 예외처리는 모두 되어있다고 생각합니다..

#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
using namespace std;
struct info {
 int weight, value;
 bool operator < (const info& b) const{
 return weight < b.weight;
 } 
};
vector<info> jewels;
vector<int> bags;
vector<pair<int,int>> max_tree;
pair<int, int> init(int start, int end, int node) {
 if (start == end) return max_tree[node] = { jewels[start].value, start };
 int mid = (start + end) / 2;
 return max_tree[node] = max(init(start, mid, node * 2), init(mid + 1, end, node * 2 + 1));
}
pair<int, int> query(int start, int end, int node, int nodeLeft, int nodeRight) {
 if (start > nodeRight || end < nodeLeft) return {-1, -1};
 if (start <= nodeLeft && end >= nodeRight) return max_tree[node];
 int mid = (nodeLeft + nodeRight) / 2;
 return max(query(start, end, node * 2, 0, mid), query(start, end, node * 2 + 1, mid + 1, nodeRight));
}
pair<int, int> update(int index, int value, int node, int nodeLeft, int nodeRight) {
 if (nodeLeft == index && nodeRight == index) return{ max_tree[node].first = value, max_tree[node].second };
 if (index < nodeLeft || index > nodeRight) return{ max_tree[node].first, max_tree[node].second };
 int mid = (nodeLeft + nodeRight) / 2;
 return max_tree[node] = max(update(index, value, node * 2, nodeLeft, mid), update(index, value, node * 2 + 1, mid + 1, nodeRight));
}
int main() {
 Fast;
 
 int n, k;
 cin >> n >> k;
 jewels.resize(n);
 bags.resize(k);
 max_tree.resize(4 * n);
 for (int i = 0; i < n;i++) {
 cin >> jewels[i].weight >> jewels[i].value;
 }
 for (int i = 0; i < k; i++) {
 cin >> bags[i];
 }
 sort(jewels.begin(), jewels.end());
 sort(bags.begin(), bags.end());
 init(0, n - 1, 1);
 ll result = 0;
 for (int i = 0; i < k; i++) {
 int limit = bags[i];
 //limit을 넘지 않는 가장 큰 인덱스
 int index = upper_bound(jewels.begin(), jewels.end(), limit, [](int limit, const info& jewel) {
 return limit < jewel.weight;
 }) - jewels.begin() - 1;
 pair<int, int> q = query(0, index, 1, 0, n - 1);
 if (q.first == -1) continue;
 result += q.first;
 update(q.second, -1, 1, 0, n - 1);
 }
 cout << result;
 return 0;
}

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

한국어 | English (Beta)

문제

문제

출처

ICPC