Submission #445464

#	Time	Username	Problem	Language	Result	Execution time	Memory
445464		MathMate	Fibonacci representations (CEOI18_fib)	C++17	100 / 100	418 ms	34132 KiB

fib

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

// Zauwazmy, ze INF musi byc wiekszy od MAX_WARTOSC + log(n)
const int INF = 2e9 + 5;
const int MOD = 1e9 + 7;

const int BASE = 1 << 18;

struct Przedzial
{
	int L, R;

	bool operator < (const Przedzial& inny) const
	{
		if(L != inny.L)
		{
			return L < inny.L;
		}

		else
		{
			return R < inny.R;
		}
	}

	bool operator == (const Przedzial& inny) const
	{
		return (L == inny.L && R == inny.R);
	}
};

struct Macierz
{
	// macierz[x][y] = macierz[najbardziej na prawo bit, ktorego nie musimy zmieniac][najbardziej na lewo bit, ktorego nie musimy zmieniac]
	int macierz[2][2];

	Macierz()
	{
		for(int i = 0; i < 2; i++)
		{
			for(int j = 0; j < 2; j++)
			{
				macierz[i][j] = 0;
			}
		}
	}

	int* operator [] (int indeks)
	{
		return macierz[indeks];
	}

	const int* operator [] (int indeks) const
	{
		return macierz[indeks];
	}

	Macierz operator * (const Macierz& inny) const
	{
		Macierz wynik;

		for(int i = 0; i < 2; i++)
		{
			for(int j = 0; j < 2; j++)
			{
				for(int k = 0; k < 2; k++)
				{
					wynik[i][k] = (wynik[i][k] + 1LL * macierz[i][j] * inny.macierz[j][k]) % MOD;
				}
			}
		}

		return wynik;
	}
};

struct Wierzcholek
{
	bool czy_istnieje = false;

	int najbardziej_na_lewo, najbardziej_na_prawo;

	Macierz macierz;

	void init(Przedzial przedzial)
	{
		najbardziej_na_lewo = przedzial.L, najbardziej_na_prawo = przedzial.R;

		int rozmiar = (najbardziej_na_prawo - najbardziej_na_lewo) / 2 + 1;

		macierz[0][0] = 1;
		macierz[0][1] = 0;
		macierz[1][0] = rozmiar - 1;
		macierz[1][1] = 1;
	}

	void combine(const Wierzcholek& a, const Wierzcholek& b)
	{
		czy_istnieje = a.czy_istnieje || b.czy_istnieje;

		if(!a.czy_istnieje)
		{
			*this = b;

			return;
		}

		if(!b.czy_istnieje)
		{
			*this = a;

			return;
		}

		najbardziej_na_lewo = a.najbardziej_na_lewo;
		najbardziej_na_prawo = b.najbardziej_na_prawo;

		const int odleglosc = b.najbardziej_na_lewo - a.najbardziej_na_prawo;

		Macierz	mid;

		if(odleglosc % 2 == 0)
		{
			mid[0][0] = 1;
			mid[1][0] = 1;
		}

		mid[0][1] = max(0, (odleglosc - 1) / 2);
		mid[1][1] = max(0, (odleglosc - 1) / 2);

		mid[1][1] = (mid[1][1] + 1) % MOD;

		macierz = (b.macierz * mid) * a.macierz;
	}
};

vector <Wierzcholek> segtree(BASE << 1);

set <Przedzial> przedzialy;

vector <vector <Przedzial>> wydarzenia;

int timer;

void update(int v)
{
	v += BASE;

	segtree[v].czy_istnieje = !segtree[v].czy_istnieje;

	// dzielimy v przez 2
	v >>= 1;

	while(v)
	{
		// mnozymy razy 2
		int lewy_syn = v << 1;

		// mnozymy razy 2 i dodajemy 1
		int prawy_syn = (v << 1) + 1;

		segtree[v].combine(segtree[lewy_syn], segtree[prawy_syn]);

		// dzielimy v przez 2
		v >>= 1;
	}
}

Wierzcholek query(Wierzcholek& start)
{
	Wierzcholek wynik;

	wynik.combine(start, segtree[1]);

	return wynik;
}


void dodaj_jesli_niepuste(int L, int R)
{
	if(L <= R)
	{
		wydarzenia[timer].push_back({L, R});

		przedzialy.insert({L, R});
	}
}

void usun(set <Przedzial>::iterator it)
{
	wydarzenia[timer].push_back({it->L, it->R});

	przedzialy.erase(it);
}

void dodaj_na_zewnatrz(const int liczba)
{
	auto R = przedzialy.upper_bound({liczba, INF});

	if(liczba + 1 == R->L)
	{
		// tuz przed przedzialem R
		// caly przedzial kompresowujemy do R->R + 1

		const int nowa_wartosc = R->R + 1;

		usun(R);

		dodaj_na_zewnatrz(nowa_wartosc);

		return;
	}

	auto L = prev(R);

	if(L->R + 1 == liczba)
	{
		// tuz za przedzialem L
		// usuwamy ostatni element przedzialu L

		dodaj_jesli_niepuste(L->L, L->R - 2);

		usun(L);

		dodaj_na_zewnatrz(liczba + 1);

		return;
	}

	Przedzial nowy_przedzial = {liczba, liczba};

	if(liczba + 2 == R->L)
	{
		nowy_przedzial.R = R->R;

		usun(R);
	}

	if(L->R + 2 == liczba)
	{
		nowy_przedzial.L = L->L;

		usun(L);
	}

	dodaj_jesli_niepuste(nowy_przedzial.L, nowy_przedzial.R);
}

void dodaj_mozliwe_do_wewnatrz(const int liczba)
{
	auto it = przedzialy.upper_bound({liczba, INF});

	it--;

	if(!(it->L <= liczba && liczba <= it->R))
	{
		dodaj_na_zewnatrz(liczba);

		return;
	}

	// Teraz juz wiemy, ze liczba jest w przedziale

	if(it->L % 2 != liczba % 2)
	{
		// Mamy przypadek dodania do 0 w ciagu ...01010...

		//   ...001010101010100...
		// +            1
		// = ...001010100000010...

		dodaj_jesli_niepuste(it->L, liczba - 1);

		const int nowa_wartosc = it->R + 1;

		usun(it);

		dodaj_na_zewnatrz(nowa_wartosc);

		return;
	}

	// Mamy przypadek dodania do 1 w ciagu ...01010...

	//   ...001010101010100...
	// +           1
	// = ...100101011010100...
	// = ...100101000000010...

	const vector <int> nowe_wartosci = {it->L - 2, it->R + 1};

	dodaj_jesli_niepuste(it->L + 1, liczba - 1);

	usun(it);

	for(auto a : nowe_wartosci)
	{
		if(a == -2)
		{
			// Fibonacci[-2] = 0

			continue;
		}

		if(a == -1)
		{
			// Fibonacci[-1] = Fibonacci[0]

			a = 0;
		}

		dodaj_na_zewnatrz(a);
	}
}

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

	int n;
	cin >> n;

	wydarzenia.resize(n);

	// Dla latwiejszej implementacji dodajemy dwa przedzialy

	przedzialy.insert({-INF, -INF});
	przedzialy.insert({INF, INF});

	for(timer = 0; timer < n; timer++)
	{
		int liczba;
		cin >> liczba;

		liczba--;

		dodaj_mozliwe_do_wewnatrz(liczba);
	}

	vector <Przedzial> wszystkie;

	for(auto& wydarzenie : wydarzenia)
	{
		for(auto& x : wydarzenie)
		{
			wszystkie.push_back(x);
		}
	}

	sort(wszystkie.begin(), wszystkie.end());

	wszystkie.resize(unique(wszystkie.begin(), wszystkie.end()) - wszystkie.begin());

	for(int i = 0; i < (int) wszystkie.size(); i++)
	{
		segtree[BASE + i].init(wszystkie[i]);
	}

	Wierzcholek start;

	start.init({-1, -1});
	start.czy_istnieje = true;

	for(timer = 0; timer < n; timer++)
	{
		for(auto& x : wydarzenia[timer])
		{
			int v = lower_bound(wszystkie.begin(),wszystkie.end(), x) - wszystkie.begin();

			update(v);
		}

		Wierzcholek wynik = query(start);

		cout << wynik.macierz[1][1] << "\n";
	}

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 35 / 35