글 읽기 - 북서풍 런타임에러..

tlsdorye 5년 전 0

어디서 나는지 알 수 있을까요?

몇번 생각해봤는데 찾기가 쉽지 않네요 ㅠ

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

class node
{
public:
	ll x, y, idx;
	node(ll x, ll y)
	{
		this->x = x;
		this->y = y;
		idx = 0;
	}
};

bool sortByX(node &u, node &v)
{
	if (u.x < v.x) return true;
	else if (u.x > v.x) return false;
	else
	{
		if (u.y > v.y) return true;
		else return false;
	}
}

bool sortByY(node &u, node &v)
{
	if (u.y > v.y) return true;
	else if (u.y < v.y) return false;
	else
	{
		if (u.x < v.x) return true;
		else return false;
	}
}

ll test_case, N, T[250000], ans;
vector<node> S;

ll build(ll n, ll s, ll e)
{
	if (s == e) return T[n] = 1;
	return T[n] = build(n * 2, s, (s + e) / 2) + build(n * 2 + 1, (s + e) / 2 + 1, e);
}

void update(ll n, ll s, ll e, ll idx)
{
	if (idx < s || e < idx) return;
	T[n]--;
	if (s == e) return;
	update(n * 2, s, (s + e) / 2, idx);
	update(n * 2 + 1, (s + e) / 2 + 1, e, idx);
}

ll query(ll n, ll s, ll e, ll l, ll r)
{
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return T[n];
	return query(n * 2, s, (s + e) / 2, l, r) + query(n * 2 + 1, (s + e) / 2 + 1, e, l, r);
}

void printNode()
{
	printf("\nNode: ");
	for (int i = 0; i < N; i++)
		printf("[%lld %lld %lld] ", S[i].x, S[i].y, S[i].idx);
	printf("\n");
}

void printTree()
{
	printf("\nTree: ");
	for (int i = 0; i < 3*N; i++)
		printf("%lld ", T[i]);
	printf("\n");
}


int main()
{
	cin >> test_case;
	while (test_case--)
	{
		cin >> N;
		ll x, y;
		for (int i = 0; i < N; i++)
		{
			scanf("%lld %lld", &x, &y);
			S.push_back(node(x, y));
		}
		sort(S.begin(), S.end(), sortByX);
		for (int i = 0; i < S.size(); i++)
			S[i].idx = i+1;
		//printNode();
		sort(S.begin(), S.end(), sortByY);
		//printNode();
		build(1,1,N);
		//printTree();
		for (int i = 0; i < N; i++)
		{
			//ll result = query(1, 1, N, S[i].idx, N) - 1;
			ans += query(1, 1, N, S[i].idx, N) - 1;
			update(1, 1, N, S[i].idx);
			//printTree();
			//printf("result: %d\n", result);
		}
		printf("%lld\n", ans);

		S.clear();
		memset(T, sizeof(T), 0);
		ans = 0;
	}
}

rhs0266 5년 전 1

lazy propagation으로 segment tree update를 수행하면 최악의 경우 n*4 의 index까지 들어가게 됩니다. 따라서 75,000*4=300,000 까지 접근이 가능해야 하므로 T[]의 사이즈를 늘려주세요.

팁을 드리면 sort 함수는 아래와 같이 구현 가능합니다.

bool sortByX(node &u, node &v)
{
	return (u.x != v.x) ? (u.x < v.x) : (u.y > v.y);
}

tlsdorye 5년 전 0

조언 감사합니다..
압도적 감사!

sort (comp) 함수도 짧아서 보기 좋네요.

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

문제

문제

출처

ICPC

북서풍 런타임에러..

tlsdorye 5년 전 0

rhs0266 5년 전 1

tlsdorye 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말