글 읽기 - MLE가 어디서 날까요?

flappybird 3년 전 2

포인터로 PST를 짰는데 메모리초과가 나네요. 노드 만드는 횟수 확인해봤는데 NlgN번 만들던데 어디서 메모리초과가 나는걸까요?

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long ll;
#define MAX 1010101
#define MOD 1000000007
#define ln '\n'
ll cnt; //노드 생성 횟수(디버깅용)
struct node {
	node* left;
	node* right;
	ll val;
	node(node* l, node* r, ll val1) : left(l), right(r), val(val1) {};
	node* update(ll low, ll high, ll target, ll x) {
		if (low <= target && target <= high) {
			if (low == high) {
				cnt++;
				return new node(NULL, NULL, x + val);
			}
			ll mid = (low + high) / 2;
			cnt++;
			return new node(left->update(low, mid, target, x), right->update(mid + 1, high, target, x), x + val);
		}
		return this;
	}
};
ll query(node* loc, ll target_low, ll target_high, ll low, ll high) {
	if (!loc) return 0;
	if (low == target_low && high == target_high) return loc->val;
	ll mid = (low + high) / 2;
	if (mid >= target_high) return query(loc->left, target_low, target_high, low, mid);
	if (mid + 1 <= target_low) return query(loc->right, target_low, target_high, mid + 1, high);
	return query(loc->left, target_low, mid, low, mid) + query(loc->right, mid + 1, target_high, mid + 1, high);
}
vector<ll> arr;
vector<ll> previous_ind;
vector<node*> seg;
map<ll, ll> m;
signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll N;
	cin >> N;
	arr.resize(N + 1);
	previous_ind.resize(N + 1);
	ll i;
	for (i = 1; i <= N; i++) cin >> arr[i];
	map<ll, vector<ll>>::iterator it;
	node* tmp;
	for (i = 1; i <= N; i++) {
		if (m[arr[i]] == 0) previous_ind[i] = -1;
		else previous_ind[i] = m[arr[i]];
		m[arr[i]] = i;
	}
	seg.push_back(new node(NULL, NULL, 0));
	seg[0]->left = seg[0]->right = seg[0];
	seg.push_back(seg[0]->update(1, N, 1, 1));
	for (i = 2; i <= N; i++) {
		seg.push_back(new node(NULL, NULL, 0));
		if (previous_ind[i] != -1) tmp = seg[i - 1]->update(1, N, previous_ind[i], -1);
		else tmp = seg[i - 1];
		seg[i] = tmp->update(1, N, i, 1);
	}
	ll Q;
	cin >> Q;
	ll q = 0;
	ll a, b;
	for (i = 1; i <= Q; i++) {
		cin >> a >> b;
		a += q;
		q = query(seg[b], a, b, 1, N);
		cout << q << ln;
	}
	//cout << ln << ln << cnt << ln;
}

flappybird 3년 전 1

위 코드에서 N=10^6, 모든 배열에 1을 넣고 보니 총 4천만개 정도 생성되네요

flappybird 2년 전 1

메모리를 끔찍하게 절약해야하네요

다른 방식으로 하니 풀렸습니다.

djs100201 2년 전 3

이미 해결하셨겠지만 저도 이걸로 고통받았는데 push_back 때문인거 같네요...
push_back()이 최악의 경우에 최대크기 *2 만큼의 공간을 할당하다 보니까 생기는 문제인거 같습니다.

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

문제

문제

출처

ICPC

MLE가 어디서 날까요?

flappybird 3년 전 2

flappybird 3년 전 1

flappybird 2년 전 1

djs100201 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말