oj.uz

Submission #539190

# Submission time Handle Problem Language Result Execution time Memory
539190 2022-03-18T14:41:51 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 31396 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];

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

		if(!foi[i]) seg.a[i] = bit.query(A[i]+1), 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]);
		}

		rebuild(A);

		for(int add = 0; add < B && add+q < Q; add++) {
			int last = bs(V[q+add], A);

			if(last > X[q+add])
				seg.upd(1, 0, N-1, X[q+add], last, 1);

			for(int x : special)
				if(x < X[q+add] && A[x] > V[q+add]) ++ans[q+add];

			answer[q+add] = max(seg.query(), ans[q+add]);

			A[X[q+add]] = V[q+add];
		}

		for(int x : special)
			foi[x] = 0;
	}
	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29012 KB Output is correct
2 Correct 204 ms 29180 KB Output is correct
3 Correct 626 ms 29384 KB Output is correct
4 Correct 530 ms 29368 KB Output is correct
5 Correct 532 ms 29372 KB Output is correct
6 Correct 625 ms 29372 KB Output is correct
7 Correct 514 ms 29368 KB Output is correct
8 Correct 539 ms 29376 KB Output is correct
9 Correct 659 ms 29380 KB Output is correct
10 Correct 443 ms 29340 KB Output is correct
11 Correct 523 ms 29296 KB Output is correct
12 Correct 601 ms 29336 KB Output is correct
13 Correct 498 ms 29336 KB Output is correct
14 Correct 488 ms 29320 KB Output is correct
15 Correct 623 ms 29324 KB Output is correct
16 Correct 401 ms 29440 KB Output is correct
17 Correct 498 ms 29320 KB Output is correct
18 Correct 641 ms 29312 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29012 KB Output is correct
2 Correct 204 ms 29180 KB Output is correct
3 Correct 626 ms 29384 KB Output is correct
4 Correct 530 ms 29368 KB Output is correct
5 Correct 532 ms 29372 KB Output is correct
6 Correct 625 ms 29372 KB Output is correct
7 Correct 514 ms 29368 KB Output is correct
8 Correct 539 ms 29376 KB Output is correct
9 Correct 659 ms 29380 KB Output is correct
10 Correct 443 ms 29340 KB Output is correct
11 Correct 523 ms 29296 KB Output is correct
12 Correct 601 ms 29336 KB Output is correct
13 Correct 498 ms 29336 KB Output is correct
14 Correct 488 ms 29320 KB Output is correct
15 Correct 623 ms 29324 KB Output is correct
16 Correct 401 ms 29440 KB Output is correct
17 Correct 498 ms 29320 KB Output is correct
18 Correct 641 ms 29312 KB Output is correct
19 Correct 4274 ms 30228 KB Output is correct
20 Correct 6125 ms 30380 KB Output is correct
21 Correct 4919 ms 30380 KB Output is correct
22 Correct 5327 ms 30372 KB Output is correct
23 Correct 4717 ms 30368 KB Output is correct
24 Correct 4231 ms 30244 KB Output is correct
25 Correct 4663 ms 30324 KB Output is correct
26 Correct 4303 ms 30204 KB Output is correct
27 Correct 4700 ms 30144 KB Output is correct
28 Correct 4873 ms 30140 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4011 ms 29980 KB Output is correct
2 Execution timed out 9038 ms 31396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29012 KB Output is correct
2 Correct 204 ms 29180 KB Output is correct
3 Correct 626 ms 29384 KB Output is correct
4 Correct 530 ms 29368 KB Output is correct
5 Correct 532 ms 29372 KB Output is correct
6 Correct 625 ms 29372 KB Output is correct
7 Correct 514 ms 29368 KB Output is correct
8 Correct 539 ms 29376 KB Output is correct
9 Correct 659 ms 29380 KB Output is correct
10 Correct 443 ms 29340 KB Output is correct
11 Correct 523 ms 29296 KB Output is correct
12 Correct 601 ms 29336 KB Output is correct
13 Correct 498 ms 29336 KB Output is correct
14 Correct 488 ms 29320 KB Output is correct
15 Correct 623 ms 29324 KB Output is correct
16 Correct 401 ms 29440 KB Output is correct
17 Correct 498 ms 29320 KB Output is correct
18 Correct 641 ms 29312 KB Output is correct
19 Correct 4274 ms 30228 KB Output is correct
20 Correct 6125 ms 30380 KB Output is correct
21 Correct 4919 ms 30380 KB Output is correct
22 Correct 5327 ms 30372 KB Output is correct
23 Correct 4717 ms 30368 KB Output is correct
24 Correct 4231 ms 30244 KB Output is correct
25 Correct 4663 ms 30324 KB Output is correct
26 Correct 4303 ms 30204 KB Output is correct
27 Correct 4700 ms 30144 KB Output is correct
28 Correct 4873 ms 30140 KB Output is correct
29 Correct 4011 ms 29980 KB Output is correct
30 Execution timed out 9038 ms 31396 KB Time limit exceeded
31 Halted 0 ms 0 KB -