글 읽기 - vector 배열의 선언 위치에 따른 런타임 에러가 뜹니다.

malratz 2년 전 0

24번줄에 선언한 vector<Query> query를 25번 라인 아래에 선언하면 런타임 에러가 뜨는데, 이유가 뭘까요?

/* reference: https://justicehui.github.io/ps/2019/06/13/BOJ13548/ */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

const int MAX_N = 1e5 + 10;

int sqrtN;
struct Query {
	int idx, l, r;
	bool operator < (Query& x) {
		if(l / sqrtN != x.l / sqrtN) return l / sqrtN < x.l / sqrtN;
		return r < x.r;
	}
};

int res;
vector<Query> query;
int a[MAX_N], ans[MAX_N], cnt[MAX_N], table[MAX_N];

void add(int x) {
	if(cnt[x] != 0) table[cnt[x]]--;
	cnt[x]++; table[cnt[x]]++;
	res = max(res, cnt[x]);
}

void sub(int x) {
	table[cnt[x]]--;
	if(cnt[x] == res && !table[cnt[x]]) res--;
	cnt[x]--;
	table[cnt[x]]++;
}

int main() {
	fastio
	
	int N; cin >> N; sqrtN = sqrt(N);
	for(int i = 1; i <= N; i++) cin >> a[i];
	
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int l, r; cin >> l >> r;
		query.push_back({i, l, r});
	}
	sort(query.begin(), query.end());
	
	int l = 0, r = 0;
	for(int i = 0; i < Q; i++) {
		while(l < query[i].l) sub(a[l++]);
		while(l > query[i].l) add(a[--l]);
		while(r < query[i].r) add(a[++r]);
		while(r > query[i].r) sub(a[r--]);
		ans[query[i].idx] = res;
	}
	for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
	
	return 0;
}

becl3ver 2년 전 0

TC로 디버깅 해보니까 for문에서

while(l < query[i].l) sub(a[l++]);

이 줄이 먼저 실행되는데 sub()함수 내에서

cnt[x]가 0인 상태에서 cnt[x]--;를 실행하게 됩니다. 그러면 cnt[x]는 -1인데

그 다음에 table[cnt[x]]++를 실행하면서 table[-1]의 값을 변경하게 되네요

아마 이렇게 음수 인덱스에 접근하는 경우가 있어서 vector가 오염되서 문제가 발생하는게 아닐까 싶네요

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

문제

문제

출처

ICPC

vector 배열의 선언 위치에 따른 런타임 에러가 뜹니다.

malratz 2년 전 0

becl3ver 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말