oj.uz

Submission #539265

# Submission time Handle Problem Language Result Execution time Memory
539265 2022-03-18T15:54:34 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 31836 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 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];

			{
				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 81 ms 29140 KB Output is correct
2 Correct 159 ms 29192 KB Output is correct
3 Correct 438 ms 29352 KB Output is correct
4 Correct 508 ms 29352 KB Output is correct
5 Correct 421 ms 29268 KB Output is correct
6 Correct 460 ms 29360 KB Output is correct
7 Correct 438 ms 29520 KB Output is correct
8 Correct 409 ms 29368 KB Output is correct
9 Correct 420 ms 29312 KB Output is correct
10 Correct 404 ms 29328 KB Output is correct
11 Correct 414 ms 29336 KB Output is correct
12 Correct 417 ms 29332 KB Output is correct
13 Correct 481 ms 29320 KB Output is correct
14 Correct 454 ms 29320 KB Output is correct
15 Correct 429 ms 29324 KB Output is correct
16 Correct 467 ms 29312 KB Output is correct
17 Correct 462 ms 29308 KB Output is correct
18 Correct 414 ms 29308 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 159 ms 29192 KB Output is correct
3 Correct 438 ms 29352 KB Output is correct
4 Correct 508 ms 29352 KB Output is correct
5 Correct 421 ms 29268 KB Output is correct
6 Correct 460 ms 29360 KB Output is correct
7 Correct 438 ms 29520 KB Output is correct
8 Correct 409 ms 29368 KB Output is correct
9 Correct 420 ms 29312 KB Output is correct
10 Correct 404 ms 29328 KB Output is correct
11 Correct 414 ms 29336 KB Output is correct
12 Correct 417 ms 29332 KB Output is correct
13 Correct 481 ms 29320 KB Output is correct
14 Correct 454 ms 29320 KB Output is correct
15 Correct 429 ms 29324 KB Output is correct
16 Correct 467 ms 29312 KB Output is correct
17 Correct 462 ms 29308 KB Output is correct
18 Correct 414 ms 29308 KB Output is correct
19 Correct 3762 ms 30132 KB Output is correct
20 Correct 4662 ms 30260 KB Output is correct
21 Correct 4481 ms 30260 KB Output is correct
22 Correct 4849 ms 30248 KB Output is correct
23 Correct 4148 ms 30164 KB Output is correct
24 Correct 4507 ms 30164 KB Output is correct
25 Correct 4345 ms 30120 KB Output is correct
26 Correct 4141 ms 30152 KB Output is correct
27 Correct 4109 ms 30156 KB Output is correct
28 Correct 4406 ms 30060 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3749 ms 30304 KB Output is correct
2 Execution timed out 9077 ms 31836 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 159 ms 29192 KB Output is correct
3 Correct 438 ms 29352 KB Output is correct
4 Correct 508 ms 29352 KB Output is correct
5 Correct 421 ms 29268 KB Output is correct
6 Correct 460 ms 29360 KB Output is correct
7 Correct 438 ms 29520 KB Output is correct
8 Correct 409 ms 29368 KB Output is correct
9 Correct 420 ms 29312 KB Output is correct
10 Correct 404 ms 29328 KB Output is correct
11 Correct 414 ms 29336 KB Output is correct
12 Correct 417 ms 29332 KB Output is correct
13 Correct 481 ms 29320 KB Output is correct
14 Correct 454 ms 29320 KB Output is correct
15 Correct 429 ms 29324 KB Output is correct
16 Correct 467 ms 29312 KB Output is correct
17 Correct 462 ms 29308 KB Output is correct
18 Correct 414 ms 29308 KB Output is correct
19 Correct 3762 ms 30132 KB Output is correct
20 Correct 4662 ms 30260 KB Output is correct
21 Correct 4481 ms 30260 KB Output is correct
22 Correct 4849 ms 30248 KB Output is correct
23 Correct 4148 ms 30164 KB Output is correct
24 Correct 4507 ms 30164 KB Output is correct
25 Correct 4345 ms 30120 KB Output is correct
26 Correct 4141 ms 30152 KB Output is correct
27 Correct 4109 ms 30156 KB Output is correct
28 Correct 4406 ms 30060 KB Output is correct
29 Correct 3749 ms 30304 KB Output is correct
30 Execution timed out 9077 ms 31836 KB Time limit exceeded
31 Halted 0 ms 0 KB -