oj.uz

답안 #539222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539222 2022-03-18T15:16:39 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 32328 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 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)
			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;

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

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

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

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 29160 KB Output is correct
2 Correct 34 ms 29180 KB Output is correct
3 Correct 95 ms 29404 KB Output is correct
4 Correct 82 ms 29404 KB Output is correct
5 Correct 78 ms 29308 KB Output is correct
6 Correct 51 ms 29404 KB Output is correct
7 Correct 58 ms 29352 KB Output is correct
8 Correct 63 ms 29408 KB Output is correct
9 Correct 75 ms 29312 KB Output is correct
10 Correct 73 ms 29368 KB Output is correct
11 Correct 78 ms 29372 KB Output is correct
12 Correct 77 ms 29372 KB Output is correct
13 Correct 69 ms 29376 KB Output is correct
14 Correct 71 ms 29436 KB Output is correct
15 Correct 77 ms 29364 KB Output is correct
16 Correct 61 ms 29256 KB Output is correct
17 Correct 58 ms 29348 KB Output is correct
18 Correct 61 ms 29352 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 29160 KB Output is correct
2 Correct 34 ms 29180 KB Output is correct
3 Correct 95 ms 29404 KB Output is correct
4 Correct 82 ms 29404 KB Output is correct
5 Correct 78 ms 29308 KB Output is correct
6 Correct 51 ms 29404 KB Output is correct
7 Correct 58 ms 29352 KB Output is correct
8 Correct 63 ms 29408 KB Output is correct
9 Correct 75 ms 29312 KB Output is correct
10 Correct 73 ms 29368 KB Output is correct
11 Correct 78 ms 29372 KB Output is correct
12 Correct 77 ms 29372 KB Output is correct
13 Correct 69 ms 29376 KB Output is correct
14 Correct 71 ms 29436 KB Output is correct
15 Correct 77 ms 29364 KB Output is correct
16 Correct 61 ms 29256 KB Output is correct
17 Correct 58 ms 29348 KB Output is correct
18 Correct 61 ms 29352 KB Output is correct
19 Correct 962 ms 30260 KB Output is correct
20 Correct 1262 ms 30388 KB Output is correct
21 Correct 674 ms 30388 KB Output is correct
22 Correct 995 ms 30388 KB Output is correct
23 Correct 982 ms 30304 KB Output is correct
24 Correct 944 ms 30288 KB Output is correct
25 Correct 886 ms 30252 KB Output is correct
26 Correct 872 ms 30252 KB Output is correct
27 Correct 632 ms 30208 KB Output is correct
28 Correct 640 ms 30204 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2643 ms 30484 KB Output is correct
2 Execution timed out 9093 ms 32328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 29160 KB Output is correct
2 Correct 34 ms 29180 KB Output is correct
3 Correct 95 ms 29404 KB Output is correct
4 Correct 82 ms 29404 KB Output is correct
5 Correct 78 ms 29308 KB Output is correct
6 Correct 51 ms 29404 KB Output is correct
7 Correct 58 ms 29352 KB Output is correct
8 Correct 63 ms 29408 KB Output is correct
9 Correct 75 ms 29312 KB Output is correct
10 Correct 73 ms 29368 KB Output is correct
11 Correct 78 ms 29372 KB Output is correct
12 Correct 77 ms 29372 KB Output is correct
13 Correct 69 ms 29376 KB Output is correct
14 Correct 71 ms 29436 KB Output is correct
15 Correct 77 ms 29364 KB Output is correct
16 Correct 61 ms 29256 KB Output is correct
17 Correct 58 ms 29348 KB Output is correct
18 Correct 61 ms 29352 KB Output is correct
19 Correct 962 ms 30260 KB Output is correct
20 Correct 1262 ms 30388 KB Output is correct
21 Correct 674 ms 30388 KB Output is correct
22 Correct 995 ms 30388 KB Output is correct
23 Correct 982 ms 30304 KB Output is correct
24 Correct 944 ms 30288 KB Output is correct
25 Correct 886 ms 30252 KB Output is correct
26 Correct 872 ms 30252 KB Output is correct
27 Correct 632 ms 30208 KB Output is correct
28 Correct 640 ms 30204 KB Output is correct
29 Correct 2643 ms 30484 KB Output is correct
30 Execution timed out 9093 ms 32328 KB Time limit exceeded
31 Halted 0 ms 0 KB -