Wyszukiwania lidera w podciągach. Zadanie Kurierzy XXI OI

Question

Mam problem z kodem do zadania Kurierzy z XXI OI, moje rozwiązanie przechodzi kilka testów ale na innych wywala się podając w niektórych zapytaniach 0 jako odpowiedź zamiast poprawnego kandydata.

Idee rozwiązania wzialem z wzorcówki, czyli drzewo przedziałowe tworzymy poprzez scalanie dwóch wierzchołków w jeden (za to odpowiada metoda combine). Dzięki temu bardzo szybko możemy znaleźć kandydata na lidera w danym przedziale, jednak musimy go jeszcze sprawdzić, tzn ile razy występuje w danym przedziale, i to jest robione hurtowo żeby zyskać lepszą złożoność. Scalanie wierzchołków polega na tym, że jeżeli dwa wierzchołki są takie same to dodajemy ich krotności, a jeżeli są inne to odejmujemy większy od mniejszego.

Wydaje mi się że może coś być nie tak w drzewie przedziałowym w linijkach 62-66, ale nie wiem jak to inaczej zrobić. Ewentualnie w wypisywaniu w linijce 120, jeszcze spróbuje poszukać błędu

 O to kod:

#include <bits/stdc++.h>
using namespace std;

const int BASE = 1024 * 512;
const int MAXN = 500005;

int n, m;
int p[MAXN];

pair<int, int> segTree[2 * BASE];

int cnt[MAXN];

int a[MAXN], b[MAXN], candidate[MAXN];
vector<int>START[MAXN], KONIEC[MAXN];
int ans[MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b)
{
	pair<int, int> combined;

	if(a.first == b.first)
		combined = {a.first, a.second + b.second};

	else if(a.second > b.second)
		combined = {a.first, a.second - b.second};

	else
		combined = {b.first, b.second - a.second};

	return combined;
}

void buildTree()
{
	for(int i = n; i < 2 * n; i++)
	{
		segTree[i] = {p[i - n], 1};
	}

	for(int i = n - 1; i >= 1; i--)
	{
		segTree[i] = combine(segTree[2 * i], segTree[2 * i + 1]);
	}
}

pair<int, int> get_candidate(int a, int b, int v, int l, int r)
{
	pair<int, int> answer;
	pair<int, int> empty;
	if(b < l || r < a)
	{
		return empty;
	}

	if(a <= l && r <= b)
	{
		return segTree[v];
	}

	int mid = (l + r) / 2;
	pair<int, int> res_l = get_candidate(a, b, 2 * v, l, mid);
	pair<int, int> res_r = get_candidate(a, b, 2 * v + 1, mid + 1, r);


	return combine(res_l, res_r);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> p[i];
	}
	
	bool added = false;
	if(n%2 == 1)
	{
		n++;
		added = true;
	} 

	buildTree();

	if(added) segTree[2 * n - 1] = {0, 0};  

	for(int i = 0; i < m; i++)
	{
		cin >> a[i] >> b[i];

		pair<int, int> lider = get_candidate(a[i], b[i], 1, 1, n);
		
		candidate[i] = lider.first;

		START[a[i]].push_back(i);
		KONIEC[b[i]].push_back(i);
	}	


	for(int i = 1; i <= n; i++)
	{
		if(!START[i].empty())
		{
			for(int j = 0; j < START[i].size(); j++)
				ans[START[i].at(j)] -= cnt[candidate[START[i][j]]];
		}
	
		cnt[p[i - 1]]++;

		if(!KONIEC[i].empty())
		{
			for(int j = 0; j < KONIEC[i].size(); j++)
				ans[KONIEC[i].at(j)] += cnt[candidate[KONIEC[i][j]]];
		}
	}

	for(int i = 0; i < m; i++)
	{
		if((b[i] - a[i] + 1) / 2 < ans[i]) 
			cout << candidate[i] << '\n';
		else
			cout << 0 << '\n';
	}
}

 

Comments

Zastanawiam się czy to co robisz w linii 38 jest na pewno dobre. Ja zazwyczaj zaczynałem wstawiać elementy od jakiejś potęgi 2.

Answer 1

No jak pisał Whistleroosh w komentarzu źle budujesz drzewo przedziałowe, trzeba wstawiać do potęgi dwójki.