Submission #99757

#	Time	Username	Problem	Language	Result	Execution time	Memory
99757		luciocf	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	66 ms	49112 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int maxn = 1e6+10;

int n;

int num[maxn], qtd[maxn], soma[maxn];

int tree[4*maxn], lazy[4*maxn];

set<int> Pos[maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		if (!Pos[l].empty()) tree[node] = -soma[l-1]-(*Pos[l].begin());
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

void flush(int node, int l, int r)
{
	if (!lazy[node]) return;

	if (l != r)
	{
		lazy[2*node] += lazy[node];
		lazy[2*node+1] += lazy[node];
	}

	tree[node] += lazy[node];

	lazy[node] = 0;
}

void upd(int node, int l, int r, int a, int b, int v)
{
	flush(node, l, r);
	if (l > b || r < a) return;

	if (l >= a && r <= b)
	{
		lazy[node] += v;
		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, int a, int b)
{
	flush(node, l, r);
	if (l > b || r < a) return -2*maxn;
	if (l >= a && r <= b) return tree[node];

	int mid = (l+r)>>1;

	return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}

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

	vector<int> C;
	map<int, int> Mp;

	for (int i = 0; i < n; i++) C.push_back(A[i]);
	for (int i = 0; i < V.size(); i++) C.push_back(V[i]);

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

	int ind = 0;
	for (auto x: C)
		if (Mp.find(x) == Mp.end())
			Mp[x] = ++ind;

	for (int i = 0; i < n; i++)
	{
		num[i] = Mp[A[i]];

		qtd[num[i]]++;
		Pos[num[i]].insert(-i);
	}

	for (int i = 1; i <= ind; i++)
		soma[i] = soma[i-1] + qtd[i];

	build(1, 1, ind);

	vector<int> ans;

	for (int i = 0; i < V.size(); i++)
	{
		int pos = X[i], v = Mp[V[i]];

		upd(1, 1, ind, num[pos]+1, ind, 1);

		bool last = 0;

		if (pos == -(*Pos[num[pos]].begin())) last = 1;

		Pos[num[pos]].erase(-pos);

		if (Pos[num[pos]].empty())
			upd(1, 1, ind, num[pos], num[pos], -3*maxn-pos);
		else if (last)
			upd(1, 1, ind, num[pos], num[pos], -(*Pos[num[pos]].begin())-pos);

		num[pos] = v;

		if (!Pos[v].empty()) upd(1, 1, ind, v, v, *Pos[v].begin());
		if (Pos[v].empty()) upd(1, 1, ind, v, v, 3*maxn);
		Pos[v].insert(-pos);
		upd(1, 1, ind, v+1, ind, -1);
		upd(1, 1, ind, v, v, -(*Pos[v].begin()));

		ans.push_back(query(1, 1, ind, 1, ind));
	}

	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) C.push_back(V[i]);
                  ~~^~~~~~~~~~
bubblesort2.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++)
                  ~~^~~~~~~~~~

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