• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Wyszukiwania lidera w podciągach. Zadanie Kurierzy XXI OI

Object Storage Arubacloud
0 głosów
118 wizyt
pytanie zadane 4 lipca 2023 w Algorytmy przez nerfiko Nowicjusz (170 p.)

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';
	}
}

 

komentarz 6 lipca 2023 przez Whistleroosh Maniak (56,980 p.)
Zastanawiam się czy to co robisz w linii 38 jest na pewno dobre. Ja zazwyczaj zaczynałem wstawiać elementy od jakiejś potęgi 2.

1 odpowiedź

0 głosów
odpowiedź 16 lipca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No jak pisał Whistleroosh w komentarzu źle budujesz drzewo przedziałowe, trzeba wstawiać do potęgi dwójki.

Podobne pytania

0 głosów
3 odpowiedzi 305 wizyt
pytanie zadane 27 lutego 2023 w C i C++ przez diedassel Użytkownik (570 p.)
0 głosów
1 odpowiedź 226 wizyt
pytanie zadane 17 stycznia 2023 w C i C++ przez polandonion Mądrala (6,970 p.)
0 głosów
1 odpowiedź 513 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,536 zapytań

141,377 odpowiedzi

319,456 komentarzy

61,922 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...