oj.uz

Submission #539267

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

constexpr int maxn = 1<<20, B = 2010, 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];
		else seg.a[i] = -inf;

		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 x : special)
			FORA[x] = 0;
 
		for(int x : special)
			for(int y : special)
				if(x < y && A[x] > A[y]) ++FORA[y];

		for(int x : special)
			DENTRO[x] -= FORA[x];

		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);

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

			A[pos] = val;
			// DENTRO[pos] = ans[q+add];

			DENTRO[pos] = 0;
			for(int j = 0; j < pos; j++)
				if(!foi[j] && A[j] > val) DENTRO[pos]++;

			{
				int last = bs(A[pos], 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];
				}
			}

			int especiais = 0;
			for(int x : special)
				especiais = max(especiais, DENTRO[x] + FORA[x]);

			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 20 ms 29148 KB Output is correct
2 Correct 34 ms 29100 KB Output is correct
3 Correct 78 ms 29368 KB Output is correct
4 Correct 78 ms 29268 KB Output is correct
5 Correct 82 ms 29356 KB Output is correct
6 Correct 33 ms 29268 KB Output is correct
7 Correct 42 ms 29340 KB Output is correct
8 Correct 52 ms 29368 KB Output is correct
9 Correct 67 ms 29356 KB Output is correct
10 Correct 75 ms 29332 KB Output is correct
11 Correct 65 ms 29308 KB Output is correct
12 Correct 63 ms 29340 KB Output is correct
13 Correct 62 ms 29224 KB Output is correct
14 Correct 58 ms 29296 KB Output is correct
15 Correct 62 ms 29332 KB Output is correct
16 Correct 42 ms 29268 KB Output is correct
17 Correct 47 ms 29260 KB Output is correct
18 Correct 42 ms 29228 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29148 KB Output is correct
2 Correct 34 ms 29100 KB Output is correct
3 Correct 78 ms 29368 KB Output is correct
4 Correct 78 ms 29268 KB Output is correct
5 Correct 82 ms 29356 KB Output is correct
6 Correct 33 ms 29268 KB Output is correct
7 Correct 42 ms 29340 KB Output is correct
8 Correct 52 ms 29368 KB Output is correct
9 Correct 67 ms 29356 KB Output is correct
10 Correct 75 ms 29332 KB Output is correct
11 Correct 65 ms 29308 KB Output is correct
12 Correct 63 ms 29340 KB Output is correct
13 Correct 62 ms 29224 KB Output is correct
14 Correct 58 ms 29296 KB Output is correct
15 Correct 62 ms 29332 KB Output is correct
16 Correct 42 ms 29268 KB Output is correct
17 Correct 47 ms 29260 KB Output is correct
18 Correct 42 ms 29228 KB Output is correct
19 Correct 371 ms 30116 KB Output is correct
20 Correct 490 ms 30280 KB Output is correct
21 Correct 335 ms 30256 KB Output is correct
22 Correct 443 ms 30260 KB Output is correct
23 Correct 355 ms 30196 KB Output is correct
24 Correct 353 ms 30168 KB Output is correct
25 Correct 313 ms 30116 KB Output is correct
26 Correct 373 ms 30112 KB Output is correct
27 Correct 267 ms 30044 KB Output is correct
28 Correct 292 ms 30048 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 30260 KB Output is correct
2 Correct 3390 ms 32048 KB Output is correct
3 Correct 7662 ms 33880 KB Output is correct
4 Correct 7516 ms 33916 KB Output is correct
5 Correct 7253 ms 33896 KB Output is correct
6 Correct 6899 ms 33992 KB Output is correct
7 Correct 6505 ms 33856 KB Output is correct
8 Correct 6802 ms 33896 KB Output is correct
9 Correct 6945 ms 33864 KB Output is correct
10 Correct 5134 ms 33620 KB Output is correct
11 Correct 5391 ms 33516 KB Output is correct
12 Correct 4955 ms 33612 KB Output is correct
13 Correct 5551 ms 33228 KB Output is correct
14 Correct 5672 ms 33320 KB Output is correct
15 Correct 5712 ms 33216 KB Output is correct
16 Correct 6652 ms 32716 KB Output is correct
17 Correct 6815 ms 32676 KB Output is correct
18 Correct 7204 ms 32704 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29148 KB Output is correct
2 Correct 34 ms 29100 KB Output is correct
3 Correct 78 ms 29368 KB Output is correct
4 Correct 78 ms 29268 KB Output is correct
5 Correct 82 ms 29356 KB Output is correct
6 Correct 33 ms 29268 KB Output is correct
7 Correct 42 ms 29340 KB Output is correct
8 Correct 52 ms 29368 KB Output is correct
9 Correct 67 ms 29356 KB Output is correct
10 Correct 75 ms 29332 KB Output is correct
11 Correct 65 ms 29308 KB Output is correct
12 Correct 63 ms 29340 KB Output is correct
13 Correct 62 ms 29224 KB Output is correct
14 Correct 58 ms 29296 KB Output is correct
15 Correct 62 ms 29332 KB Output is correct
16 Correct 42 ms 29268 KB Output is correct
17 Correct 47 ms 29260 KB Output is correct
18 Correct 42 ms 29228 KB Output is correct
19 Correct 371 ms 30116 KB Output is correct
20 Correct 490 ms 30280 KB Output is correct
21 Correct 335 ms 30256 KB Output is correct
22 Correct 443 ms 30260 KB Output is correct
23 Correct 355 ms 30196 KB Output is correct
24 Correct 353 ms 30168 KB Output is correct
25 Correct 313 ms 30116 KB Output is correct
26 Correct 373 ms 30112 KB Output is correct
27 Correct 267 ms 30044 KB Output is correct
28 Correct 292 ms 30048 KB Output is correct
29 Correct 246 ms 30260 KB Output is correct
30 Correct 3390 ms 32048 KB Output is correct
31 Correct 7662 ms 33880 KB Output is correct
32 Correct 7516 ms 33916 KB Output is correct
33 Correct 7253 ms 33896 KB Output is correct
34 Correct 6899 ms 33992 KB Output is correct
35 Correct 6505 ms 33856 KB Output is correct
36 Correct 6802 ms 33896 KB Output is correct
37 Correct 6945 ms 33864 KB Output is correct
38 Correct 5134 ms 33620 KB Output is correct
39 Correct 5391 ms 33516 KB Output is correct
40 Correct 4955 ms 33612 KB Output is correct
41 Correct 5551 ms 33228 KB Output is correct
42 Correct 5672 ms 33320 KB Output is correct
43 Correct 5712 ms 33216 KB Output is correct
44 Correct 6652 ms 32716 KB Output is correct
45 Correct 6815 ms 32676 KB Output is correct
46 Correct 7204 ms 32704 KB Output is correct
47 Execution timed out 9023 ms 56300 KB Time limit exceeded
48 Halted 0 ms 0 KB -