Submission #512918

#	Time	Username	Problem	Language	Result	Execution time	Memory
512918		MathMate	Wall (IOI14_wall)	C++17	0 / 100	40 ms	33136 KiB

wall

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

const int INF = 1e9 + 5;
const int BASE = 1 << 21;

struct Wierzcholek
{
	int min_wartosc, max_wartosc;
};

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

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

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

	segtree[lewy_syn].max_wartosc = min(segtree[lewy_syn].max_wartosc, segtree[v].max_wartosc);
	segtree[lewy_syn].max_wartosc = max(segtree[lewy_syn].max_wartosc, segtree[v].min_wartosc);

	segtree[prawy_syn].max_wartosc = min(segtree[prawy_syn].max_wartosc, segtree[v].max_wartosc);
	segtree[prawy_syn].max_wartosc = max(segtree[prawy_syn].max_wartosc, segtree[v].min_wartosc);

	segtree[lewy_syn].min_wartosc = max(segtree[lewy_syn].min_wartosc, segtree[v].min_wartosc);
	segtree[lewy_syn].min_wartosc = min(segtree[lewy_syn].min_wartosc, segtree[v].max_wartosc);

	segtree[prawy_syn].min_wartosc = max(segtree[prawy_syn].min_wartosc, segtree[v].min_wartosc);
	segtree[prawy_syn].min_wartosc = min(segtree[prawy_syn].min_wartosc, segtree[v].max_wartosc);

	segtree[v].min_wartosc = -INF;
	segtree[v].max_wartosc = INF;
}

void update_maksuj(int L, int R, int wartosc, int v = 1, int a = 1, int b = BASE)
{
	if(b < L || a > R)
	{
		return;
	}

	if(L <= a && b <= R)
	{
		segtree[v].min_wartosc = max(segtree[v].min_wartosc, wartosc);
		segtree[v].max_wartosc = max(segtree[v].max_wartosc, wartosc);

		return;
	}

	push(v);

	int mid = (a + b) / 2;

	// mnozymy razy 2
	int lewy_syn = v << 1;

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

	update_maksuj(L, R, wartosc, lewy_syn, a, mid);
	update_maksuj(L, R, wartosc, prawy_syn, mid + 1, b);
}

void update_minimuj(int L, int R, int wartosc, int v = 1, int a = 1, int b = BASE)
{
	if(b < L || a > R)
	{
		return;
	}

	if(L <= a && b <= R)
	{
		segtree[v].min_wartosc = min(segtree[v].min_wartosc, wartosc);
		segtree[v].max_wartosc = min(segtree[v].max_wartosc, wartosc);

		return;
	}

	push(v);

	int mid = (a + b) / 2;

	// mnozymy razy 2
	int lewy_syn = v << 1;

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

	update_minimuj(L, R, wartosc, lewy_syn, a, mid);
	update_minimuj(L, R, wartosc, prawy_syn, mid + 1, b);
}

int query(int v)
{
	v += BASE;

	int wynik = segtree[v].max_wartosc;

	return wynik;
}

void buildWall(int n, int t, int operacje[], int L[], int R[], int wartosci[], int odpowiedzi[])
{
	for(int i = 1; i < BASE; i++)
	{
		segtree[i].min_wartosc = -INF;
		segtree[i].max_wartosc = INF;
	}

	for(int i = 0; i < t; i++)
	{
		if(operacje[i] == 0)
		{
			update_minimuj(L[i], R[i], wartosci[i]);
		}

		// if(operacje[i] == 1)
		else
		{
			update_maksuj(L[i], R[i], wartosci[i]);
		}
	}

	for(int i = 1; i < BASE; i++)
	{
		push(i);
	}

	for(int i = 0; i < n; i++)
	{
		odpowiedzi[i] = query(i);
	}
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39