oj.uz

Submission #539261

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

constexpr int maxn = 1<<20, B = 8010, 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]);
		}

		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 58 ms 29100 KB Output is correct
2 Correct 172 ms 29160 KB Output is correct
3 Correct 1800 ms 29300 KB Output is correct
4 Correct 1740 ms 29300 KB Output is correct
5 Correct 1715 ms 29388 KB Output is correct
6 Correct 438 ms 29292 KB Output is correct
7 Correct 925 ms 29296 KB Output is correct
8 Correct 1259 ms 29296 KB Output is correct
9 Correct 1806 ms 29296 KB Output is correct
10 Correct 1301 ms 29280 KB Output is correct
11 Correct 1293 ms 29280 KB Output is correct
12 Correct 1277 ms 29272 KB Output is correct
13 Correct 1375 ms 29268 KB Output is correct
14 Correct 1379 ms 29276 KB Output is correct
15 Correct 1387 ms 29268 KB Output is correct
16 Correct 1349 ms 29248 KB Output is correct
17 Correct 1316 ms 29260 KB Output is correct
18 Correct 1333 ms 29268 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29100 KB Output is correct
2 Correct 172 ms 29160 KB Output is correct
3 Correct 1800 ms 29300 KB Output is correct
4 Correct 1740 ms 29300 KB Output is correct
5 Correct 1715 ms 29388 KB Output is correct
6 Correct 438 ms 29292 KB Output is correct
7 Correct 925 ms 29296 KB Output is correct
8 Correct 1259 ms 29296 KB Output is correct
9 Correct 1806 ms 29296 KB Output is correct
10 Correct 1301 ms 29280 KB Output is correct
11 Correct 1293 ms 29280 KB Output is correct
12 Correct 1277 ms 29272 KB Output is correct
13 Correct 1375 ms 29268 KB Output is correct
14 Correct 1379 ms 29276 KB Output is correct
15 Correct 1387 ms 29268 KB Output is correct
16 Correct 1349 ms 29248 KB Output is correct
17 Correct 1316 ms 29260 KB Output is correct
18 Correct 1333 ms 29268 KB Output is correct
19 Execution timed out 9084 ms 29912 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9066 ms 29608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29100 KB Output is correct
2 Correct 172 ms 29160 KB Output is correct
3 Correct 1800 ms 29300 KB Output is correct
4 Correct 1740 ms 29300 KB Output is correct
5 Correct 1715 ms 29388 KB Output is correct
6 Correct 438 ms 29292 KB Output is correct
7 Correct 925 ms 29296 KB Output is correct
8 Correct 1259 ms 29296 KB Output is correct
9 Correct 1806 ms 29296 KB Output is correct
10 Correct 1301 ms 29280 KB Output is correct
11 Correct 1293 ms 29280 KB Output is correct
12 Correct 1277 ms 29272 KB Output is correct
13 Correct 1375 ms 29268 KB Output is correct
14 Correct 1379 ms 29276 KB Output is correct
15 Correct 1387 ms 29268 KB Output is correct
16 Correct 1349 ms 29248 KB Output is correct
17 Correct 1316 ms 29260 KB Output is correct
18 Correct 1333 ms 29268 KB Output is correct
19 Execution timed out 9084 ms 29912 KB Time limit exceeded
20 Halted 0 ms 0 KB -