Submission #67232

#	Time	Username	Problem	Language	Result	Execution time	Memory
67232		MatheusLealV	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	5576 ms	237596 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define N 1000050
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
using namespace std;
typedef long long ll;

int inf = 2000000000;

int n, v[N], c, bit[N], lim;

vector<int> val;

map<int, int> mapa;

set<int> pos[N];

struct T
{
	int tree[4*N], lazy[4*N];

	inline void init()
	{
		for(int i = 0; i < 4*N; i++) lazy[i] = tree[i] = 0;
	}

	inline void prop(int nod, int a, int b)
	{
		if(!lazy[nod]) return;

		tree[nod] += lazy[nod];

		if(a != b)
		{
			lazy[l] += lazy[nod];

			lazy[r] += lazy[nod];
		}

		lazy[nod] = 0;

		return;
	}

	void upd(int nod, int a, int b, int i, int j, int x)
	{
		prop(nod, a, b);

		if(j < a or i > b) return;

		if(i <= a and j >= b)
		{
			tree[nod] += x;

			if(a != b)
			{
				lazy[l] += x;

				lazy[r] += x;
			}

			return;
		}

		upd(l, a, mid, i, j, x), upd(r, mid + 1, b, i, j, x);

		tree[nod] = max(tree[l], tree[r]);
	}

	int query(int nod, int a, int b, int i, int j)
	{
		prop(nod, a, b);

		if(j < a or i > b) return -inf;

		if(i <= a and j >= b) return tree[nod];

		return max(query(l, a, mid, i, j), query(r, mid + 1, b, i, j));
	}

} Tree;

inline void remove(int x, int po)
{
	Tree.upd(1, 1, lim, x, lim, 1);

	int p = -(*pos[x].begin());

	pos[x].erase(-po);

	if(p == po)
	{
		int pp = -(*pos[x].begin());

		Tree.upd(1, 1, lim, x, x, pp - p);
	}
}

inline void add(int x, int po)
{
	Tree.upd(1, 1, lim, x, lim, -1);

	int p = -(*pos[x].begin());

	if(po > p)
	{
		Tree.upd(1, 1, lim, x, x, po - p);
	}

	pos[x].insert(-po);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	int Q = X.size();

	n = A.size();

	for(auto x: A) val.push_back(x);

	for(auto x: V) val.push_back(x);

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

	for(auto x: val) if(!mapa[x]) mapa[x] = ++c;

	for(int i = 0; i < N; i ++) pos[i].insert(10000);

	for(int i = 0; i < n; i++) v[i] = mapa[A[i]];

	for(int i = 0; i < Q; i++) V[i] = mapa[V[i]];

	for(int i = 0; i < n; i++) pos[v[i]].insert(-i);

	vector<int> answer(Q);

	Tree.init();

	lim = N - 1;

	for(int i = 0, soma = 0; i < N; i++)
	{
		soma += pos[i].size() - 1;

		if(pos[i].empty()) continue;

		int x = -(*pos[i].begin());

		Tree.upd(1, 1, lim, i, i, x - soma);
	}

	for(int j = 0; j < Q; j++)
	{
		int x = X[j], val = v[X[j]], novo = V[j];

		remove(val, x);

		add(novo, x);

		v[x] = novo;

		answer[j] = 1 + Tree.query(1, 1, lim, 1, lim);
	}

	return answer;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40