Submission #548099

#	Time	Username	Problem	Language	Result	Execution time	Memory
548099		blue	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4002 ms	211776 KiB

bubblesort2

#include "bubblesort2.h"
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
 
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

set<int> inds[1'000'000];
 
struct sdata
{
	int currans;
	int count;
};
 
sdata combine(sdata X, sdata Y)
{
	sdata res;
	res.count = X.count + Y.count;
	res.currans = max(X.currans, Y.currans - X.count);
	return res;
}
 
int N, Q;
vi A;
 
struct segtree
{
	int Z;
	vi l, r;
	vector<sdata> s;
 
	void build(int i, int L, int R)
	{
		l[i] = L;
		r[i] = R;
		if(L == R)
		{
			s[i].currans = (inds[l[i]].empty() ? -3'000'000 : *inds[l[i]].rbegin());
			s[i].count = sz(inds[l[i]]);
		}
		else
		{
			int m = (L+R)/2;
			build(2*i, L, m);
			build(2*i+1, m+1, R);
			s[i] = combine(s[2*i], s[2*i+1]);
		}
 
		// cerr << L << ' ' << R << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
 
	segtree(int K)
	{
		Z = 4*K;
 
		l = r = vi(1+Z);
		s = vector<sdata>(1+Z);
 
		build(1, 0, K-1);
	}
 
	void insert(int i, int p, int id)
	{
		if(l[i] == r[i])
		{
			inds[l[i]].insert(id);
			s[i].currans = max(s[i].currans, id);
			s[i].count++;
		}
		else
		{
			if(p <= (l[i]+r[i])/2)
				insert(2*i, p, id);
			else
				insert(2*i+1, p, id);
 
			s[i] = combine(s[2*i], s[2*i+1]);
		}
 
		// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
 
	void erase(int i, int p, int id)
	{
		if(l[i] == r[i])
		{
			inds[l[i]].erase(id);
			s[i].count--;
			s[i].currans = (inds[l[i]].empty() ? -3'000'000 : *inds[l[i]].rbegin());
		}
		else
		{
			if(p <= (l[i]+r[i])/2)
				erase(2*i, p, id);
			else
				erase(2*i+1, p, id);
 
			s[i] = combine(s[2*i], s[2*i+1]);
		}

		// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
};
 
vi countScans(vi A_, vi X, vi V)
{
	A = A_;
	N = sz(A);
	Q = sz(X);
 
	map<pii, int> vals;
	for(int i = 0; i < N; i++)
		vals[{A[i], i}] = 0;
 
	for(int j = 0; j < Q; j++)
		vals[{V[j], X[j]}] = 0;
 
	int ct = -1;
	for(auto& z : vals)
	{
		z.second = ++ct;

		// cerr << z.first.first << " - " << z.second << '\n';
	}
 
	// cerr << "values # = " << sz(vals) << '\n';
 
	vi answer(Q);


 
 

	for(int i = 0; i < N; i++)
		inds[vals[{A[i], i}]].insert(i);

	segtree S(N+Q);
 
	// for(int i = 0; i < N; i++)
	// {
	// 	S.insert(1, vals[{A[i], i}], i);
	// }
 
	for(int j = 0; j < Q; j++)
	{
		S.erase(1, vals[{A[X[j]], X[j]}], X[j]);
		A[X[j]] = V[j];
		S.insert(1, vals[{A[X[j]], X[j]}], X[j]);
 
		answer[j] = S.s[1].currans;
	}
 
	return answer;
}

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