oj.uz

Submission #539257

# Submission time Handle Problem Language Result Execution time Memory
539257 2022-03-18T15:47:18 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 4682 ms 30516 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 98 ms 29012 KB Output is correct
2 Correct 145 ms 29164 KB Output is correct
3 Correct 390 ms 29340 KB Output is correct
4 Correct 395 ms 29348 KB Output is correct
5 Correct 376 ms 29332 KB Output is correct
6 Correct 417 ms 29336 KB Output is correct
7 Correct 403 ms 29468 KB Output is correct
8 Correct 393 ms 29260 KB Output is correct
9 Correct 384 ms 29336 KB Output is correct
10 Correct 367 ms 29312 KB Output is correct
11 Correct 372 ms 29268 KB Output is correct
12 Correct 444 ms 29308 KB Output is correct
13 Correct 391 ms 29424 KB Output is correct
14 Correct 376 ms 29292 KB Output is correct
15 Correct 369 ms 29356 KB Output is correct
16 Correct 377 ms 29288 KB Output is correct
17 Correct 377 ms 29388 KB Output is correct
18 Correct 368 ms 29284 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 29012 KB Output is correct
2 Correct 145 ms 29164 KB Output is correct
3 Correct 390 ms 29340 KB Output is correct
4 Correct 395 ms 29348 KB Output is correct
5 Correct 376 ms 29332 KB Output is correct
6 Correct 417 ms 29336 KB Output is correct
7 Correct 403 ms 29468 KB Output is correct
8 Correct 393 ms 29260 KB Output is correct
9 Correct 384 ms 29336 KB Output is correct
10 Correct 367 ms 29312 KB Output is correct
11 Correct 372 ms 29268 KB Output is correct
12 Correct 444 ms 29308 KB Output is correct
13 Correct 391 ms 29424 KB Output is correct
14 Correct 376 ms 29292 KB Output is correct
15 Correct 369 ms 29356 KB Output is correct
16 Correct 377 ms 29288 KB Output is correct
17 Correct 377 ms 29388 KB Output is correct
18 Correct 368 ms 29284 KB Output is correct
19 Correct 2836 ms 30356 KB Output is correct
20 Correct 3611 ms 30516 KB Output is correct
21 Correct 3539 ms 30388 KB Output is correct
22 Correct 3890 ms 30388 KB Output is correct
23 Correct 3781 ms 30148 KB Output is correct
24 Correct 3700 ms 30272 KB Output is correct
25 Correct 4532 ms 30196 KB Output is correct
26 Correct 4596 ms 30096 KB Output is correct
27 Correct 4682 ms 30160 KB Output is correct
28 Correct 4671 ms 30160 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 29012 KB Output is correct
2 Correct 145 ms 29164 KB Output is correct
3 Correct 390 ms 29340 KB Output is correct
4 Correct 395 ms 29348 KB Output is correct
5 Correct 376 ms 29332 KB Output is correct
6 Correct 417 ms 29336 KB Output is correct
7 Correct 403 ms 29468 KB Output is correct
8 Correct 393 ms 29260 KB Output is correct
9 Correct 384 ms 29336 KB Output is correct
10 Correct 367 ms 29312 KB Output is correct
11 Correct 372 ms 29268 KB Output is correct
12 Correct 444 ms 29308 KB Output is correct
13 Correct 391 ms 29424 KB Output is correct
14 Correct 376 ms 29292 KB Output is correct
15 Correct 369 ms 29356 KB Output is correct
16 Correct 377 ms 29288 KB Output is correct
17 Correct 377 ms 29388 KB Output is correct
18 Correct 368 ms 29284 KB Output is correct
19 Correct 2836 ms 30356 KB Output is correct
20 Correct 3611 ms 30516 KB Output is correct
21 Correct 3539 ms 30388 KB Output is correct
22 Correct 3890 ms 30388 KB Output is correct
23 Correct 3781 ms 30148 KB Output is correct
24 Correct 3700 ms 30272 KB Output is correct
25 Correct 4532 ms 30196 KB Output is correct
26 Correct 4596 ms 30096 KB Output is correct
27 Correct 4682 ms 30160 KB Output is correct
28 Correct 4671 ms 30160 KB Output is correct
29 Incorrect 3969 ms 29696 KB Output isn't correct
30 Halted 0 ms 0 KB -