글 읽기 - 시간 초과가 뜹니다.

qsccsq22 1년 전 0

각 구간에서 merge sort로 노드들을 합쳐주면서 누적합까지 관리해주고 있습니다.

get_max에서 lower_bound와 upper_bound로 index 찾아주면서 합을 확인하고 있는데 어디에서 시간초과가 날까요..

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
vector <vector<ll>> node;
vector <vector<pair<ll, ll>>> segtree;
vector <pair<ll, ll>> value;
vector <ll> parent;
vector <ll> sz;
vector <ll> depth;
vector <ll> section;
vector <ll> chain_number;
vector <ll> chain_index;
vector <vector<ll>> chain;
ll N, Q, u, v, mn, mx, cnt;

bool compare(pair<ll, ll> a, pair<ll, ll> b)
{
	return a.first < b.first;
}
void DFS(ll n, ll pn)
{
	parent[n] = pn;
	sz[n] = cnt++;
	for (ll x : node[n])
		if (x != pn)
			DFS(x, n);
	sz[n] = cnt - sz[n];
}

void HLD(ll n, ll pn, ll start_chain, ll d)
{
	depth[n] = d;
	chain_number[n] = start_chain;
	chain_index[n] = chain[start_chain].size();
	chain[start_chain].push_back(n);
	section[n] = cnt++;
	value[cnt].second = value[n].first;

	ll heavy = -1;
	for (ll x : node[n])
		if (x != pn && (heavy == -1 || sz[heavy] < sz[x]))
			heavy = x;
	if (heavy != -1)
		HLD(heavy, n, start_chain, d);

	for (ll x : node[n])
		if (x != pn && x != heavy)
			HLD(x, n, x, d + 1);
}

ll LCA(ll u, ll v)
{
	while (chain_number[u] != chain_number[v])
	{
		if (depth[u] > depth[v])
			u = parent[chain_number[u]];
		else
			v = parent[chain_number[v]];
	}
	return chain_index[u] > chain_index[v] ? v : u;
}

void set_segtree(ll n, ll start, ll end)
{
	if (start == end)
		segtree[n].push_back(make_pair(value[start + 1].second, value[start + 1].second));
	else
	{
		set_segtree(n * 2, start, (start + end) / 2);
		set_segtree(n * 2 + 1, (start + end) / 2 + 1, end);
		segtree[n].resize(segtree[n * 2].size() + segtree[n * 2 + 1].size());
		ll l = 0, r = 0, total = 0;
		while (l < segtree[n * 2].size() && r < segtree[n * 2 + 1].size())
		{
			if (segtree[n * 2][l].first < segtree[n * 2 + 1][r].first)
			{
				segtree[n][total] = { segtree[n * 2][l].first, segtree[n * 2][l].first };
				if (total != 0)
					segtree[n][total].second += segtree[n][total - 1].second;
				l++;
				total++;
			}
			else
			{
				segtree[n][total] = { segtree[n * 2 + 1][r].first, segtree[n * 2 + 1][r].first };
				if (total != 0)
					segtree[n][total].second += segtree[n][total - 1].second;
				r++;
				total++;
			}
		}
		if (l != segtree[n * 2].size())
		{
			while (l < segtree[n * 2].size())
			{
				segtree[n][total] = segtree[n * 2][l++];
				segtree[n][total].second += segtree[n][total - 1].second;
				total++;
			}
		}
		else
		{
			while (r < segtree[n * 2 + 1].size())
			{
				segtree[n][total] = segtree[n * 2 + 1][r++];
				segtree[n][total].second += segtree[n][total - 1].second;
				total++;
			}
		}
	}
}

ll get_max(ll n, ll start, ll end, ll left, ll right, ll mn, ll mx)
{
	if (right < start || left > end)
		return 0;
	if (left <= start && end <= right)
	{
		ll L = lower_bound(segtree[n].begin(), segtree[n].end(), pair<ll, ll>(mn, 0), compare) - segtree[n].begin();
		ll R = upper_bound(segtree[n].begin(), segtree[n].end(), pair<ll, ll>(mx, 0), compare) - segtree[n].begin();
		ll L_SUM = (L > 0 ? segtree[n][L - 1].second : 0);
		ll R_SUM = (R == 0 ? 0 : segtree[n][R - 1].second);
		return R_SUM - L_SUM;
	}
	return get_max(n * 2, start, (start + end) / 2, left, right, mn, mx) + get_max(n * 2 + 1, (start + end) / 2 + 1, end, left, right, mn, mx);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;

	ll h = (ll)ceil(log2(N));
	segtree = vector<vector<pair<ll, ll>>>((1 << (h + 1)));
	value = vector<pair<ll, ll>>(N + 1);
	node = vector<vector<ll>>(N + 1);
	parent = vector<ll>(N + 1);
	sz = vector<ll>(N + 1);
	depth = vector<ll>(N + 1);
	chain_number = vector<ll>(N + 1);
	chain_index = vector<ll>(N + 1);
	section = vector<ll>(N + 1);
	chain = vector<vector<ll>>(N + 1);

	for (ll i = 1; i <= N; i++)
		cin >> value[i].first;

	for (ll i = 0; i < N - 1; i++)
	{
		cin >> u >> v;
		node[u].push_back(v);
	}

	cnt = 0;
	DFS(1, 0);
	cnt = 0;
	HLD(1, 0, 1, 0);

	set_segtree(1, 0, N - 1);

	for (ll i = 0; i < Q; i++)
	{
		cin >> u >> v >> mn >> mx;
		ll t = LCA(u, v);
		ll sum = 0;
		while (chain_number[t] != chain_number[u])
		{
			sum += get_max(1, 0, N - 1, section[chain_number[u]], section[u], mn, mx);
			u = parent[chain_number[u]];
		}
		sum += get_max(1, 0, N - 1, section[t], section[u], mn, mx);
		while (chain_number[t] != chain_number[v])
		{
			sum += get_max(1, 0, N - 1, section[chain_number[v]], section[v], mn, mx);
			v = parent[chain_number[v]];
		}
		sum += get_max(1, 0, N - 1, section[t] + 1, section[v], mn, mx);
		cout << sum << '\n';
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과가 뜹니다.

qsccsq22 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말