oj.uz

Submission #512917

# Submission time Handle Problem Language Result Execution time Memory
512917 2022-01-16T19:57:09 Z MathMate Wall (IOI14_wall) C++17
0 / 100
 29 ms 33100 KB 
#include <bits/stdc++.h>
using namespace std;

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

struct Wierzcholek
{
	int min_wartosc = -INF, max_wartosc = INF;
};

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 = 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 33100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 33036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 33056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 32996 KB Output isn't correct
2 Halted 0 ms 0 KB -