Submission #539236

#	Time	Username	Problem	Language	Result	Execution time	Memory
539236		LucaDantas	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9029 ms	31676 KiB

bubblesort2

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

constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
// constexpr int maxn = 1<<20, B = 700, inf = 0x3f3f3f3f; // subtasks brutao, mudar

struct SegmentTree {
	int tree[maxn], lazy[maxn], a[maxn];
	void flush(int node, int i, int j) {
		if(!lazy[node]) return;
		if(i != j) {
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
		}
		tree[node] += lazy[node];
		lazy[node] = 0;
	}
	void build(int node, int i, int j) {
		lazy[node] = 0;
		if(i == j) return (void)(tree[node] = a[i]);
		int m = (i+j) >> 1;
		build(node<<1, i, m);
		build(node<<1|1, m+1, j);
		tree[node] = max(tree[node<<1], tree[node<<1|1]);
	}
	void upd(int node, int i, int j, int l, int r, int v) {
		flush(node, i, j);
		if(i > r || j < l) return;
		if(i >= l && j <= r) {
			lazy[node] += v;
			flush(node, i, j);
			return;
		}
		int m = (i+j) >> 1;
		upd(node<<1, i, m, l, r, v);
		upd(node<<1|1, m+1, j, l, r, v);
		tree[node] = max(tree[node<<1], tree[node<<1|1]);
	}
	int query() { return tree[1] + lazy[1]; } // quero o maximo geral mesmo
} seg;

void compress(vector<int>& A, vector<int>& V) {
	map<int,int> mp;
	for(int x : A)
		mp[x] = 0;
	for(int x : V)
		mp[x] = 0;
 
	int coord = 0;
	for(auto& it : mp)
		it.second = ++coord;
 
	for(int& x : A)
		x = mp[x];
	for(int& x : V)
		x = mp[x];
}

struct BIT {
	int bit[maxn];
	void upd(int x, int v) {
		for(; x > 0; x -= x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x < maxn; x += x&-x)
			ans += bit[x];
		return ans;
	}
	void clear() { memset(bit, 0, sizeof bit); }
} bit;
 
vector<int> pareto;

int ans[maxn]; bool foi[maxn];
vector<pair<int,int>> qr[maxn];
int FORA[maxn], DENTRO[maxn];

void rebuild(const vector<int>& A) {
	pareto.clear();
	int N = (int)(A.size());
	for(int i = 0; i < N; i++) {
		if(foi[i]) continue;
		while(pareto.size() && A[i] <= A[pareto.back()])
			pareto.pop_back();
		pareto.push_back(i);
	}

	bit.clear();
	for(int i = 0; i < (int)A.size(); i++) {
		while(qr[i].size()) {
			auto [val, id] = qr[i].back();
			qr[i].pop_back();
			ans[id] = bit.query(val+1);
		}

		DENTRO[i] = bit.query(A[i]+1);
		if(!foi[i]) seg.a[i] = DENTRO[i], bit.upd(A[i], 1);
		else seg.a[i] = -inf;
	}
	seg.build(1, 0, N-1);
}

int bs(int x, const vector<int>& A) {
	int l = 0, r = (int)(pareto.size())-1, ans = -1;
	while(l <= r) {
		int m = (l+r) >> 1;
		if(A[pareto[m]] < x)
			ans = pareto[m], l = m+1;
		else
			r = m-1;
	}
	return ans;
}

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

	std::vector<int> answer(Q);
	for(int q = 0; q < Q; q += B) {
		vector<int> special;

		for(int add = 0; add < B && add+q < Q; add++) {
			qr[X[q+add]].push_back({V[q+add], q+add});
			if(foi[X[q+add]]) continue;
			foi[X[q+add]] = 1;
			special.push_back(X[q+add]);
		}

		/* for(int i = 0; i < N; i++)
			if(!foi[i]) foi[i] = 1, special.push_back(i); */

		rebuild(A);

		// memset(FORA, 0, sizeof FORA);
		// memset(ans, 0, sizeof ans);

		/* for(int x : special)
			FORA[x] = 0;

		for(int x : special)
			for(int y : special)
				if(x < y && A[x] > A[y]) ++FORA[y]; */

		for(int add = 0; add < B && add+q < Q; add++) {
			int pos = X[q+add], val = V[q+add];

			int last = bs(val, A);

			if(last > pos)
				seg.upd(1, 0, N-1, pos, last, 1);

			/* for(int x : special) {
				if(pos < x && A[pos] > A[x]) --FORA[x];
				if(x < pos && A[x] > A[pos]) --FORA[pos];
			} */

			// DENTRO[pos] = ans[q+add];
			A[pos] = val;
			// db
			/* DENTRO[pos] = 0;
			for(int j = 0; j < pos; j++)
				if(!foi[j] && A[j] > val) DENTRO[pos]++; */

			/* for(int x : special) {
				if(pos < x && A[pos] > A[x]) ++FORA[x];
				if(x < pos && A[x] > A[pos]) ++FORA[pos];
			} */

			int especiais = 0;
			for(int x : special) {
				// especiais = max(especiais, FORA[x] + DENTRO[x]);
				int aq = 0;
				for(int j = 0; j < x; j++)
					aq += A[j] > A[x];
				especiais = max(especiais, aq);
			}

			answer[q+add] = max(seg.query(), especiais);
		}

		for(int x : special)
			foi[x] = 0;
	}
	return answer;
}

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