oj.uz

Submission #539259

# Submission time Handle Problem Language Result Execution time Memory
539259 2022-03-18T15:47:48 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 5153 ms 30204 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

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

struct SegmentTree {
	int a[maxn];
	void build(int node, int i, int j) {
	}
	void upd(int node, int i, int j, int l, int r, int v) {
		for(int i = l; i <= r; i++)
			a[i] += v;
	}
	int query() {
		int ans = 0;
		for(int i = 0; i < 8010; i++)
			ans = max(ans, a[i]);
		return ans;
	}
} 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];
		else seg.a[i] = -inf;

		// if(!foi[i])
		bit.upd(A[i], 1);
	}
	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);

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

			{
				int last = bs(A[pos], A);
				if(last > pos)
					seg.upd(1, 0, N-1, pos, last, -1);
			}

			A[pos] = val;

			{
				int last = bs(A[pos], A);
				if(last > pos)
					seg.upd(1, 0, N-1, pos, last, 1);
			}

			int especiais = 0;
			for(int x : special) {
				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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 29104 KB Output is correct
2 Correct 161 ms 29140 KB Output is correct
3 Correct 466 ms 29292 KB Output is correct
4 Correct 530 ms 29296 KB Output is correct
5 Correct 455 ms 29300 KB Output is correct
6 Correct 502 ms 29288 KB Output is correct
7 Correct 517 ms 29292 KB Output is correct
8 Correct 478 ms 29268 KB Output is correct
9 Correct 461 ms 29544 KB Output is correct
10 Correct 526 ms 29396 KB Output is correct
11 Correct 535 ms 29268 KB Output is correct
12 Correct 472 ms 29268 KB Output is correct
13 Correct 518 ms 29268 KB Output is correct
14 Correct 485 ms 29268 KB Output is correct
15 Correct 527 ms 29268 KB Output is correct
16 Correct 541 ms 29140 KB Output is correct
17 Correct 517 ms 29240 KB Output is correct
18 Correct 467 ms 29248 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 29104 KB Output is correct
2 Correct 161 ms 29140 KB Output is correct
3 Correct 466 ms 29292 KB Output is correct
4 Correct 530 ms 29296 KB Output is correct
5 Correct 455 ms 29300 KB Output is correct
6 Correct 502 ms 29288 KB Output is correct
7 Correct 517 ms 29292 KB Output is correct
8 Correct 478 ms 29268 KB Output is correct
9 Correct 461 ms 29544 KB Output is correct
10 Correct 526 ms 29396 KB Output is correct
11 Correct 535 ms 29268 KB Output is correct
12 Correct 472 ms 29268 KB Output is correct
13 Correct 518 ms 29268 KB Output is correct
14 Correct 485 ms 29268 KB Output is correct
15 Correct 527 ms 29268 KB Output is correct
16 Correct 541 ms 29140 KB Output is correct
17 Correct 517 ms 29240 KB Output is correct
18 Correct 467 ms 29248 KB Output is correct
19 Correct 4300 ms 30200 KB Output is correct
20 Correct 5153 ms 30204 KB Output is correct
21 Correct 4672 ms 30196 KB Output is correct
22 Correct 4746 ms 30180 KB Output is correct
23 Correct 4600 ms 29964 KB Output is correct
24 Correct 4729 ms 30096 KB Output is correct
25 Correct 4822 ms 30048 KB Output is correct
26 Correct 4947 ms 30052 KB Output is correct
27 Correct 4906 ms 29896 KB Output is correct
28 Correct 4993 ms 30012 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 29104 KB Output is correct
2 Correct 161 ms 29140 KB Output is correct
3 Correct 466 ms 29292 KB Output is correct
4 Correct 530 ms 29296 KB Output is correct
5 Correct 455 ms 29300 KB Output is correct
6 Correct 502 ms 29288 KB Output is correct
7 Correct 517 ms 29292 KB Output is correct
8 Correct 478 ms 29268 KB Output is correct
9 Correct 461 ms 29544 KB Output is correct
10 Correct 526 ms 29396 KB Output is correct
11 Correct 535 ms 29268 KB Output is correct
12 Correct 472 ms 29268 KB Output is correct
13 Correct 518 ms 29268 KB Output is correct
14 Correct 485 ms 29268 KB Output is correct
15 Correct 527 ms 29268 KB Output is correct
16 Correct 541 ms 29140 KB Output is correct
17 Correct 517 ms 29240 KB Output is correct
18 Correct 467 ms 29248 KB Output is correct
19 Correct 4300 ms 30200 KB Output is correct
20 Correct 5153 ms 30204 KB Output is correct
21 Correct 4672 ms 30196 KB Output is correct
22 Correct 4746 ms 30180 KB Output is correct
23 Correct 4600 ms 29964 KB Output is correct
24 Correct 4729 ms 30096 KB Output is correct
25 Correct 4822 ms 30048 KB Output is correct
26 Correct 4947 ms 30052 KB Output is correct
27 Correct 4906 ms 29896 KB Output is correct
28 Correct 4993 ms 30012 KB Output is correct
29 Incorrect 3689 ms 29796 KB Output isn't correct
30 Halted 0 ms 0 KB -