oj.uz

Submission #539275

# Submission time Handle Problem Language Result Execution time Memory
539275 2022-03-18T16:04:18 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 53948 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, bit2;
 
vector<int> pareto;

int DENTRO_NA_QUERY[maxn]; bool foi[maxn];
vector<pair<int,int>> qr[maxn];
int FORA[maxn], DENTRO[maxn], FORA_INI[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();
			DENTRO_NA_QUERY[id] = bit2.query(val+1);
		}

		DENTRO[i] = bit.query(A[i]+1);

		if(!foi[i]) seg.a[i] = bit.query(A[i]+1);
		else seg.a[i] = -inf;

		bit.upd(A[i], 1);
		if(!foi[i])
			bit2.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] = DENTRO_NA_QUERY[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 22 ms 29176 KB Output is correct
2 Correct 28 ms 29140 KB Output is correct
3 Correct 70 ms 29392 KB Output is correct
4 Correct 71 ms 29396 KB Output is correct
5 Correct 64 ms 29396 KB Output is correct
6 Correct 31 ms 29396 KB Output is correct
7 Correct 41 ms 29396 KB Output is correct
8 Correct 51 ms 29336 KB Output is correct
9 Correct 66 ms 29300 KB Output is correct
10 Correct 57 ms 29364 KB Output is correct
11 Correct 57 ms 29372 KB Output is correct
12 Correct 56 ms 29284 KB Output is correct
13 Correct 53 ms 29356 KB Output is correct
14 Correct 53 ms 29268 KB Output is correct
15 Correct 54 ms 29268 KB Output is correct
16 Correct 38 ms 29320 KB Output is correct
17 Correct 38 ms 29268 KB Output is correct
18 Correct 37 ms 29360 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29176 KB Output is correct
2 Correct 28 ms 29140 KB Output is correct
3 Correct 70 ms 29392 KB Output is correct
4 Correct 71 ms 29396 KB Output is correct
5 Correct 64 ms 29396 KB Output is correct
6 Correct 31 ms 29396 KB Output is correct
7 Correct 41 ms 29396 KB Output is correct
8 Correct 51 ms 29336 KB Output is correct
9 Correct 66 ms 29300 KB Output is correct
10 Correct 57 ms 29364 KB Output is correct
11 Correct 57 ms 29372 KB Output is correct
12 Correct 56 ms 29284 KB Output is correct
13 Correct 53 ms 29356 KB Output is correct
14 Correct 53 ms 29268 KB Output is correct
15 Correct 54 ms 29268 KB Output is correct
16 Correct 38 ms 29320 KB Output is correct
17 Correct 38 ms 29268 KB Output is correct
18 Correct 37 ms 29360 KB Output is correct
19 Correct 357 ms 30200 KB Output is correct
20 Correct 439 ms 30284 KB Output is correct
21 Correct 309 ms 30340 KB Output is correct
22 Correct 385 ms 30464 KB Output is correct
23 Correct 335 ms 30352 KB Output is correct
24 Correct 317 ms 30356 KB Output is correct
25 Correct 281 ms 30176 KB Output is correct
26 Correct 283 ms 30188 KB Output is correct
27 Correct 231 ms 30240 KB Output is correct
28 Correct 230 ms 30132 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 30280 KB Output is correct
2 Correct 2746 ms 32244 KB Output is correct
3 Correct 6444 ms 33332 KB Output is correct
4 Correct 6554 ms 33332 KB Output is correct
5 Correct 6453 ms 33332 KB Output is correct
6 Correct 6491 ms 33336 KB Output is correct
7 Correct 5713 ms 33316 KB Output is correct
8 Correct 5910 ms 33328 KB Output is correct
9 Correct 5903 ms 33328 KB Output is correct
10 Correct 4291 ms 33044 KB Output is correct
11 Correct 4279 ms 32972 KB Output is correct
12 Correct 4250 ms 33004 KB Output is correct
13 Correct 5054 ms 32756 KB Output is correct
14 Correct 5158 ms 32712 KB Output is correct
15 Correct 5038 ms 32908 KB Output is correct
16 Correct 5879 ms 32428 KB Output is correct
17 Correct 5918 ms 32384 KB Output is correct
18 Correct 6005 ms 32228 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 29176 KB Output is correct
2 Correct 28 ms 29140 KB Output is correct
3 Correct 70 ms 29392 KB Output is correct
4 Correct 71 ms 29396 KB Output is correct
5 Correct 64 ms 29396 KB Output is correct
6 Correct 31 ms 29396 KB Output is correct
7 Correct 41 ms 29396 KB Output is correct
8 Correct 51 ms 29336 KB Output is correct
9 Correct 66 ms 29300 KB Output is correct
10 Correct 57 ms 29364 KB Output is correct
11 Correct 57 ms 29372 KB Output is correct
12 Correct 56 ms 29284 KB Output is correct
13 Correct 53 ms 29356 KB Output is correct
14 Correct 53 ms 29268 KB Output is correct
15 Correct 54 ms 29268 KB Output is correct
16 Correct 38 ms 29320 KB Output is correct
17 Correct 38 ms 29268 KB Output is correct
18 Correct 37 ms 29360 KB Output is correct
19 Correct 357 ms 30200 KB Output is correct
20 Correct 439 ms 30284 KB Output is correct
21 Correct 309 ms 30340 KB Output is correct
22 Correct 385 ms 30464 KB Output is correct
23 Correct 335 ms 30352 KB Output is correct
24 Correct 317 ms 30356 KB Output is correct
25 Correct 281 ms 30176 KB Output is correct
26 Correct 283 ms 30188 KB Output is correct
27 Correct 231 ms 30240 KB Output is correct
28 Correct 230 ms 30132 KB Output is correct
29 Correct 207 ms 30280 KB Output is correct
30 Correct 2746 ms 32244 KB Output is correct
31 Correct 6444 ms 33332 KB Output is correct
32 Correct 6554 ms 33332 KB Output is correct
33 Correct 6453 ms 33332 KB Output is correct
34 Correct 6491 ms 33336 KB Output is correct
35 Correct 5713 ms 33316 KB Output is correct
36 Correct 5910 ms 33328 KB Output is correct
37 Correct 5903 ms 33328 KB Output is correct
38 Correct 4291 ms 33044 KB Output is correct
39 Correct 4279 ms 32972 KB Output is correct
40 Correct 4250 ms 33004 KB Output is correct
41 Correct 5054 ms 32756 KB Output is correct
42 Correct 5158 ms 32712 KB Output is correct
43 Correct 5038 ms 32908 KB Output is correct
44 Correct 5879 ms 32428 KB Output is correct
45 Correct 5918 ms 32384 KB Output is correct
46 Correct 6005 ms 32228 KB Output is correct
47 Execution timed out 9103 ms 53948 KB Time limit exceeded
48 Halted 0 ms 0 KB -