oj.uz

Submission #539236

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

constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
// constexpr int maxn = 1<<20, B = 700, 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], bit.upd(A[i], 1);
		else seg.a[i] = -inf;
	}
	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);

		// memset(FORA, 0, sizeof FORA);
		// memset(ans, 0, sizeof ans);

		/* 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 add = 0; add < B && add+q < Q; add++) {
			int pos = X[q+add], val = V[q+add];

			int last = bs(val, 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];
			} */

			// DENTRO[pos] = ans[q+add];
			A[pos] = val;
			// db
			/* DENTRO[pos] = 0;
			for(int j = 0; j < pos; j++)
				if(!foi[j] && A[j] > val) DENTRO[pos]++; */

			/* 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, FORA[x] + DENTRO[x]);
				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 29140 KB Output is correct
2 Correct 136 ms 29196 KB Output is correct
3 Correct 403 ms 29616 KB Output is correct
4 Correct 394 ms 29396 KB Output is correct
5 Correct 400 ms 29396 KB Output is correct
6 Correct 377 ms 29512 KB Output is correct
7 Correct 388 ms 29512 KB Output is correct
8 Correct 407 ms 29516 KB Output is correct
9 Correct 395 ms 29516 KB Output is correct
10 Correct 383 ms 29384 KB Output is correct
11 Correct 399 ms 29356 KB Output is correct
12 Correct 372 ms 29424 KB Output is correct
13 Correct 377 ms 29340 KB Output is correct
14 Correct 372 ms 29472 KB Output is correct
15 Correct 428 ms 29472 KB Output is correct
16 Correct 369 ms 29376 KB Output is correct
17 Correct 376 ms 29344 KB Output is correct
18 Correct 450 ms 29464 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 29140 KB Output is correct
2 Correct 136 ms 29196 KB Output is correct
3 Correct 403 ms 29616 KB Output is correct
4 Correct 394 ms 29396 KB Output is correct
5 Correct 400 ms 29396 KB Output is correct
6 Correct 377 ms 29512 KB Output is correct
7 Correct 388 ms 29512 KB Output is correct
8 Correct 407 ms 29516 KB Output is correct
9 Correct 395 ms 29516 KB Output is correct
10 Correct 383 ms 29384 KB Output is correct
11 Correct 399 ms 29356 KB Output is correct
12 Correct 372 ms 29424 KB Output is correct
13 Correct 377 ms 29340 KB Output is correct
14 Correct 372 ms 29472 KB Output is correct
15 Correct 428 ms 29472 KB Output is correct
16 Correct 369 ms 29376 KB Output is correct
17 Correct 376 ms 29344 KB Output is correct
18 Correct 450 ms 29464 KB Output is correct
19 Correct 3137 ms 30388 KB Output is correct
20 Correct 4382 ms 30588 KB Output is correct
21 Correct 4316 ms 30412 KB Output is correct
22 Correct 4081 ms 30652 KB Output is correct
23 Correct 3959 ms 30400 KB Output is correct
24 Correct 4666 ms 30288 KB Output is correct
25 Correct 4910 ms 30240 KB Output is correct
26 Correct 4799 ms 30236 KB Output is correct
27 Correct 3910 ms 30436 KB Output is correct
28 Correct 4085 ms 30312 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4053 ms 30240 KB Output is correct
2 Execution timed out 9029 ms 31676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 29140 KB Output is correct
2 Correct 136 ms 29196 KB Output is correct
3 Correct 403 ms 29616 KB Output is correct
4 Correct 394 ms 29396 KB Output is correct
5 Correct 400 ms 29396 KB Output is correct
6 Correct 377 ms 29512 KB Output is correct
7 Correct 388 ms 29512 KB Output is correct
8 Correct 407 ms 29516 KB Output is correct
9 Correct 395 ms 29516 KB Output is correct
10 Correct 383 ms 29384 KB Output is correct
11 Correct 399 ms 29356 KB Output is correct
12 Correct 372 ms 29424 KB Output is correct
13 Correct 377 ms 29340 KB Output is correct
14 Correct 372 ms 29472 KB Output is correct
15 Correct 428 ms 29472 KB Output is correct
16 Correct 369 ms 29376 KB Output is correct
17 Correct 376 ms 29344 KB Output is correct
18 Correct 450 ms 29464 KB Output is correct
19 Correct 3137 ms 30388 KB Output is correct
20 Correct 4382 ms 30588 KB Output is correct
21 Correct 4316 ms 30412 KB Output is correct
22 Correct 4081 ms 30652 KB Output is correct
23 Correct 3959 ms 30400 KB Output is correct
24 Correct 4666 ms 30288 KB Output is correct
25 Correct 4910 ms 30240 KB Output is correct
26 Correct 4799 ms 30236 KB Output is correct
27 Correct 3910 ms 30436 KB Output is correct
28 Correct 4085 ms 30312 KB Output is correct
29 Correct 4053 ms 30240 KB Output is correct
30 Execution timed out 9029 ms 31676 KB Time limit exceeded
31 Halted 0 ms 0 KB -