oj.uz

Submission #445389

# Submission time Handle Problem Language Result Execution time Memory
445389 2021-07-17T20:39:45 Z MathMate Fibonacci representations (CEOI18_fib) C++17
65 / 100
 307 ms 46376 KB 
#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 << 17;

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

	else
	{
		// 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7472 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7420 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7500 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7472 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7420 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7500 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7400 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7500 KB Output is correct
2 Correct 4 ms 7504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7472 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7420 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7500 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7400 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 4 ms 7500 KB Output is correct
14 Correct 4 ms 7504 KB Output is correct
15 Correct 4 ms 7500 KB Output is correct
16 Correct 6 ms 7500 KB Output is correct
17 Correct 4 ms 7500 KB Output is correct
18 Correct 4 ms 7500 KB Output is correct
19 Correct 4 ms 7500 KB Output is correct
20 Correct 5 ms 7436 KB Output is correct
21 Correct 5 ms 7508 KB Output is correct
22 Correct 5 ms 7500 KB Output is correct
23 Correct 5 ms 7508 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 202 ms 20448 KB Output is correct
3 Correct 220 ms 19488 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7472 KB Output is correct
3 Correct 4 ms 7500 KB Output is correct
4 Correct 4 ms 7420 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7500 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7400 KB Output is correct
11 Correct 5 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 4 ms 7500 KB Output is correct
14 Correct 4 ms 7504 KB Output is correct
15 Correct 4 ms 7500 KB Output is correct
16 Correct 6 ms 7500 KB Output is correct
17 Correct 4 ms 7500 KB Output is correct
18 Correct 4 ms 7500 KB Output is correct
19 Correct 4 ms 7500 KB Output is correct
20 Correct 5 ms 7436 KB Output is correct
21 Correct 5 ms 7508 KB Output is correct
22 Correct 5 ms 7500 KB Output is correct
23 Correct 5 ms 7508 KB Output is correct
24 Correct 5 ms 7500 KB Output is correct
25 Correct 202 ms 20448 KB Output is correct
26 Correct 220 ms 19488 KB Output is correct
27 Correct 56 ms 11464 KB Output is correct
28 Correct 95 ms 14040 KB Output is correct
29 Correct 67 ms 12968 KB Output is correct
30 Correct 100 ms 13736 KB Output is correct
31 Correct 140 ms 17196 KB Output is correct
32 Correct 119 ms 15160 KB Output is correct
33 Correct 178 ms 17208 KB Output is correct
34 Correct 196 ms 17096 KB Output is correct
35 Correct 215 ms 15528 KB Output is correct
36 Correct 248 ms 17208 KB Output is correct
37 Correct 215 ms 16336 KB Output is correct
38 Correct 209 ms 20416 KB Output is correct
39 Correct 96 ms 15672 KB Output is correct
40 Correct 152 ms 18828 KB Output is correct
41 Correct 307 ms 19204 KB Output is correct
42 Correct 206 ms 20412 KB Output is correct
43 Correct 167 ms 19848 KB Output is correct
44 Runtime error 141 ms 46376 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -