oj.uz

Submission #539260

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

constexpr int maxn = 1<<20, B = 2, 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 81 ms 29096 KB Output is correct
2 Correct 136 ms 29076 KB Output is correct
3 Correct 309 ms 29420 KB Output is correct
4 Correct 296 ms 29288 KB Output is correct
5 Correct 284 ms 29388 KB Output is correct
6 Correct 272 ms 29260 KB Output is correct
7 Correct 258 ms 29292 KB Output is correct
8 Correct 274 ms 29424 KB Output is correct
9 Correct 279 ms 29292 KB Output is correct
10 Correct 265 ms 29268 KB Output is correct
11 Correct 277 ms 29268 KB Output is correct
12 Correct 269 ms 29268 KB Output is correct
13 Correct 261 ms 29268 KB Output is correct
14 Correct 292 ms 29268 KB Output is correct
15 Correct 264 ms 29268 KB Output is correct
16 Correct 277 ms 29364 KB Output is correct
17 Correct 265 ms 29372 KB Output is correct
18 Correct 262 ms 29248 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 29096 KB Output is correct
2 Correct 136 ms 29076 KB Output is correct
3 Correct 309 ms 29420 KB Output is correct
4 Correct 296 ms 29288 KB Output is correct
5 Correct 284 ms 29388 KB Output is correct
6 Correct 272 ms 29260 KB Output is correct
7 Correct 258 ms 29292 KB Output is correct
8 Correct 274 ms 29424 KB Output is correct
9 Correct 279 ms 29292 KB Output is correct
10 Correct 265 ms 29268 KB Output is correct
11 Correct 277 ms 29268 KB Output is correct
12 Correct 269 ms 29268 KB Output is correct
13 Correct 261 ms 29268 KB Output is correct
14 Correct 292 ms 29268 KB Output is correct
15 Correct 264 ms 29268 KB Output is correct
16 Correct 277 ms 29364 KB Output is correct
17 Correct 265 ms 29372 KB Output is correct
18 Correct 262 ms 29248 KB Output is correct
19 Correct 2231 ms 30052 KB Output is correct
20 Correct 2758 ms 30196 KB Output is correct
21 Correct 2626 ms 30196 KB Output is correct
22 Correct 2718 ms 30188 KB Output is correct
23 Correct 2648 ms 30100 KB Output is correct
24 Correct 2604 ms 30224 KB Output is correct
25 Correct 2639 ms 30168 KB Output is correct
26 Correct 2612 ms 29928 KB Output is correct
27 Correct 2648 ms 30128 KB Output is correct
28 Correct 2448 ms 30000 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 29096 KB Output is correct
2 Correct 136 ms 29076 KB Output is correct
3 Correct 309 ms 29420 KB Output is correct
4 Correct 296 ms 29288 KB Output is correct
5 Correct 284 ms 29388 KB Output is correct
6 Correct 272 ms 29260 KB Output is correct
7 Correct 258 ms 29292 KB Output is correct
8 Correct 274 ms 29424 KB Output is correct
9 Correct 279 ms 29292 KB Output is correct
10 Correct 265 ms 29268 KB Output is correct
11 Correct 277 ms 29268 KB Output is correct
12 Correct 269 ms 29268 KB Output is correct
13 Correct 261 ms 29268 KB Output is correct
14 Correct 292 ms 29268 KB Output is correct
15 Correct 264 ms 29268 KB Output is correct
16 Correct 277 ms 29364 KB Output is correct
17 Correct 265 ms 29372 KB Output is correct
18 Correct 262 ms 29248 KB Output is correct
19 Correct 2231 ms 30052 KB Output is correct
20 Correct 2758 ms 30196 KB Output is correct
21 Correct 2626 ms 30196 KB Output is correct
22 Correct 2718 ms 30188 KB Output is correct
23 Correct 2648 ms 30100 KB Output is correct
24 Correct 2604 ms 30224 KB Output is correct
25 Correct 2639 ms 30168 KB Output is correct
26 Correct 2612 ms 29928 KB Output is correct
27 Correct 2648 ms 30128 KB Output is correct
28 Correct 2448 ms 30000 KB Output is correct
29 Incorrect 1939 ms 29772 KB Output isn't correct
30 Halted 0 ms 0 KB -