글 읽기 - RTE 나는이유와 속도 향상 방법 질문

sgc109 7년 전 0

로컬에서는 문제없이 돌아가는데 BOJ에 제출하면 RTE가 납니다. 제 생각에 out of range 는 아닌것같고

메모리를 너무 많이 잡아서 나는것같다는 추측을 하고있는데(원래 이럴때 메모리초과 보다 RTE가 먼저나나요?)

vector<pii> 네개가 각각 4000만의 크기를 갖게되는데 메모리제한을 훨씬 초과하는것같습니다.

그래서 세그트리의 최대 right 를 x,y 좌표의 최대값인 약 10^7에서 줄여야할 것같은데 2차원 평면이고 개구리가 뛰는 거리도 있고 사각형이 겹치는 유무 같은것도 있어서 좌표압축은 좀 힘들 것같은데 혹시 방법좀 가르쳐주실수있나요?

p.s. vector<pii> 들을 pii 배열로해서 약 4000만 의크기로 잡아줬더니 RTE에서 메모리초과로 바뀌었습니다.

벡터의 최대 크기 제한이있는건가요?..

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <stack>
#include <cstring>
#include <cstdlib>
#include <string>
#include <set>
#include <cmath>
// #include <unordered_set>
// #include <map>
#define REP(i,a,b) for(int i = a; i < b;++i) 
#define FOR(i,n) REP(i,0,n)
#define mp make_pair
#define pb push_back
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > piii;

const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 100002;

struct Cord{
	int x,y;
};

vector<pii> rangeMaxXup;
vector<pii> rangeMaxXdown;
vector<pii> rangeMaxYleft;
vector<pii> rangeMaxYright;
vi adj[MAX_N];
int N,r,d;
int size;
int start;
pair<Cord,int> squares[MAX_N];

bool compX(const pair<Cord,int>& a, const pair<Cord,int>& b) {
	return a.first.x < b.first.x;
}
bool compY(const pair<Cord,int>& a, const pair<Cord,int>& b) {
	return a.first.y < b.first.y;
}
bool compI(const pair<Cord,int>& a, const pair<Cord,int>& b) {
	return a.second < b.second;
}

pii query(int nodeLeft, int nodeRight, int left, int right, int node, vector<pii>& v) {
	if(left <= nodeLeft && nodeRight <= right) {
		return v[node];
	}
	if(right < nodeLeft || nodeRight < left) return mp(-1,-1);
	int nodeMid=(nodeLeft+nodeRight)>>1;
	pii leftRange = query(nodeLeft,nodeMid,left,right,2*node,v);
	pii rightRange = query(nodeMid+1,nodeRight,left,right,2*node+1,v);
	return leftRange.first >= rightRange.first ? leftRange : rightRange;
}

void update(int nodeLeft, int nodeRight, int node, int pos, int val, int id, vector<pii>& v) {
	if(nodeLeft == nodeRight && nodeRight == pos) {
		if(v[node].first <= val) v[node] = mp(val,id);
		return;
	}
	if(pos < nodeLeft || nodeRight < pos) return;
	int nodeMid=(nodeLeft+nodeRight)>>1;
	update(nodeLeft,nodeMid,2*node,pos,val,id,v);
	update(nodeMid+1,nodeRight,2*node+1,pos,val,id,v);
	v[node] = v[2*node].first >= v[2*node+1].first ? v[2*node] : v[2*node+1];
}

void update(int pos, int val, int id, vector<pii>& v){
	update(0,size-1,1,pos,val,id,v);
}

pii query(int left, int right, vector<pii>& v) {
	return query(0,size-1,left,right,1,v);
}

int ans;
int visited[MAX_N];
queue<int> q;
void bfs(int start) {
	q.push(start);
	visited[start]=1;
	while(!q.empty()) {
		int here = q.front();
		ans = max(ans,squares[here-1].first.x+squares[here-1].first.y+2*r);
		q.pop();
		for(auto& there : adj[here]){
			if(visited[there]) continue;
			q.push(there);
			visited[there]=1;
		}
	}
}

int main() {

	inp2(N,r);
	size=10010002;
	rangeMaxXup.resize(4*size);
	rangeMaxXdown.resize(4*size);
	rangeMaxYleft.resize(4*size);
	rangeMaxYright.resize(4*size);
	FOR(i,N){
		int x,y;
		inp2(x,y);
		if(x==0&&y==0) start=i+1;
		squares[i] = mp(Cord({x,y}),i+1);
	}
	inp1(d);

	sort(squares,squares+N,compX);

	FOR(i,N) {
		auto nearestSqrUp = query(squares[i].first.y,squares[i].first.y+r,rangeMaxXup);
		if(nearestSqrUp.second != 0) {
			int dist = squares[i].first.x - nearestSqrUp.first;
			if(dist <= d) {
				adj[nearestSqrUp.second].pb(squares[i].second);
				adj[squares[i].second].pb(nearestSqrUp.second);
			}
		} 
		auto nearestSqrDown = query(squares[i].first.y,squares[i].first.y+r,rangeMaxXdown);
		if(nearestSqrDown.second != 0) {
			int dist = squares[i].first.x - nearestSqrDown.first;
			if(dist <= d) {
				adj[nearestSqrDown.second].pb(squares[i].second);
				adj[squares[i].second].pb(nearestSqrDown.second);
			}
		}
		update(squares[i].first.y+r,squares[i].first.x+r,squares[i].second,rangeMaxXup);
		update(squares[i].first.y,squares[i].first.x+r,squares[i].second,rangeMaxXdown);
	}

	sort(squares,squares+N,compY);

	FOR(i,N) {
		auto nearestSqrLeft = query(squares[i].first.x,squares[i].first.x+r,rangeMaxYleft);
		if(nearestSqrLeft.second != 0) {
			int dist = squares[i].first.y - nearestSqrLeft.first;
			if(dist <= d) {
				adj[nearestSqrLeft.second].pb(squares[i].second);
				adj[squares[i].second].pb(nearestSqrLeft.second);
			}
		} 
		auto nearestSqrRight = query(squares[i].first.x,squares[i].first.x+r,rangeMaxYright);
		if(nearestSqrRight.second != 0) {
			int dist = squares[i].first.y - nearestSqrRight.first;
			if(dist <= d) {
				adj[nearestSqrRight.second].pb(squares[i].second);
				adj[squares[i].second].pb(nearestSqrRight.second);
			}
		}
		update(squares[i].first.x,squares[i].first.y+r,squares[i].second,rangeMaxYleft);
		update(squares[i].first.x+r,squares[i].first.y+r,squares[i].second,rangeMaxYright);
	}

	sort(squares,squares+N,compI);

	bfs(start);

	printf("%d",ans);

	return 0;
}

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

문제

문제

출처

ICPC

RTE 나는이유와 속도 향상 방법 질문

sgc109 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말