oj.uz

Submission #539216

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

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

		ANS[i] = bit.query(A[i]+1);
		if(!foi[i]) seg.a[i] = ANS[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(ANS, 0, sizeof ANS);
		// memset(ans, 0, sizeof ans);


		for(int x : special)
			for(int y : special)
				if(x < y && A[x] > A[y]) ++ANS[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]) --ANS[x];
				if(x < pos && A[x] > A[pos]) --ANS[pos];
			}

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

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

			int especiais = 0;
			for(int x : special)
				especiais = max(especiais, ANS[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 23 ms 29012 KB Output is correct
2 Correct 27 ms 29096 KB Output is correct
3 Correct 74 ms 29264 KB Output is correct
4 Correct 70 ms 29272 KB Output is correct
5 Correct 68 ms 29216 KB Output is correct
6 Correct 44 ms 29268 KB Output is correct
7 Correct 48 ms 29204 KB Output is correct
8 Correct 52 ms 29204 KB Output is correct
9 Correct 57 ms 29268 KB Output is correct
10 Correct 65 ms 29140 KB Output is correct
11 Correct 59 ms 29236 KB Output is correct
12 Correct 62 ms 29244 KB Output is correct
13 Correct 52 ms 29232 KB Output is correct
14 Correct 55 ms 29204 KB Output is correct
15 Correct 57 ms 29240 KB Output is correct
16 Correct 53 ms 29148 KB Output is correct
17 Correct 57 ms 29220 KB Output is correct
18 Correct 51 ms 29216 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29012 KB Output is correct
2 Correct 27 ms 29096 KB Output is correct
3 Correct 74 ms 29264 KB Output is correct
4 Correct 70 ms 29272 KB Output is correct
5 Correct 68 ms 29216 KB Output is correct
6 Correct 44 ms 29268 KB Output is correct
7 Correct 48 ms 29204 KB Output is correct
8 Correct 52 ms 29204 KB Output is correct
9 Correct 57 ms 29268 KB Output is correct
10 Correct 65 ms 29140 KB Output is correct
11 Correct 59 ms 29236 KB Output is correct
12 Correct 62 ms 29244 KB Output is correct
13 Correct 52 ms 29232 KB Output is correct
14 Correct 55 ms 29204 KB Output is correct
15 Correct 57 ms 29240 KB Output is correct
16 Correct 53 ms 29148 KB Output is correct
17 Correct 57 ms 29220 KB Output is correct
18 Correct 51 ms 29216 KB Output is correct
19 Correct 693 ms 29860 KB Output is correct
20 Correct 888 ms 29976 KB Output is correct
21 Correct 575 ms 30032 KB Output is correct
22 Correct 663 ms 29972 KB Output is correct
23 Correct 648 ms 29904 KB Output is correct
24 Correct 676 ms 29880 KB Output is correct
25 Correct 611 ms 29836 KB Output is correct
26 Correct 625 ms 29836 KB Output is correct
27 Correct 568 ms 29784 KB Output is correct
28 Correct 570 ms 29788 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2719 ms 29548 KB Output is correct
2 Execution timed out 9103 ms 30264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29012 KB Output is correct
2 Correct 27 ms 29096 KB Output is correct
3 Correct 74 ms 29264 KB Output is correct
4 Correct 70 ms 29272 KB Output is correct
5 Correct 68 ms 29216 KB Output is correct
6 Correct 44 ms 29268 KB Output is correct
7 Correct 48 ms 29204 KB Output is correct
8 Correct 52 ms 29204 KB Output is correct
9 Correct 57 ms 29268 KB Output is correct
10 Correct 65 ms 29140 KB Output is correct
11 Correct 59 ms 29236 KB Output is correct
12 Correct 62 ms 29244 KB Output is correct
13 Correct 52 ms 29232 KB Output is correct
14 Correct 55 ms 29204 KB Output is correct
15 Correct 57 ms 29240 KB Output is correct
16 Correct 53 ms 29148 KB Output is correct
17 Correct 57 ms 29220 KB Output is correct
18 Correct 51 ms 29216 KB Output is correct
19 Correct 693 ms 29860 KB Output is correct
20 Correct 888 ms 29976 KB Output is correct
21 Correct 575 ms 30032 KB Output is correct
22 Correct 663 ms 29972 KB Output is correct
23 Correct 648 ms 29904 KB Output is correct
24 Correct 676 ms 29880 KB Output is correct
25 Correct 611 ms 29836 KB Output is correct
26 Correct 625 ms 29836 KB Output is correct
27 Correct 568 ms 29784 KB Output is correct
28 Correct 570 ms 29788 KB Output is correct
29 Correct 2719 ms 29548 KB Output is correct
30 Execution timed out 9103 ms 30264 KB Time limit exceeded
31 Halted 0 ms 0 KB -