oj.uz

답안 #539207

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

		rebuild(A);

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

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

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 29140 KB Output is correct
2 Correct 140 ms 29172 KB Output is correct
3 Correct 397 ms 29328 KB Output is correct
4 Correct 393 ms 29480 KB Output is correct
5 Correct 411 ms 29348 KB Output is correct
6 Correct 387 ms 29344 KB Output is correct
7 Correct 392 ms 29340 KB Output is correct
8 Correct 408 ms 29344 KB Output is correct
9 Correct 391 ms 29328 KB Output is correct
10 Correct 399 ms 29324 KB Output is correct
11 Correct 372 ms 29432 KB Output is correct
12 Correct 409 ms 29268 KB Output is correct
13 Correct 411 ms 29392 KB Output is correct
14 Correct 377 ms 29428 KB Output is correct
15 Correct 410 ms 29320 KB Output is correct
16 Correct 396 ms 29288 KB Output is correct
17 Correct 371 ms 29300 KB Output is correct
18 Correct 414 ms 29392 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 29140 KB Output is correct
2 Correct 140 ms 29172 KB Output is correct
3 Correct 397 ms 29328 KB Output is correct
4 Correct 393 ms 29480 KB Output is correct
5 Correct 411 ms 29348 KB Output is correct
6 Correct 387 ms 29344 KB Output is correct
7 Correct 392 ms 29340 KB Output is correct
8 Correct 408 ms 29344 KB Output is correct
9 Correct 391 ms 29328 KB Output is correct
10 Correct 399 ms 29324 KB Output is correct
11 Correct 372 ms 29432 KB Output is correct
12 Correct 409 ms 29268 KB Output is correct
13 Correct 411 ms 29392 KB Output is correct
14 Correct 377 ms 29428 KB Output is correct
15 Correct 410 ms 29320 KB Output is correct
16 Correct 396 ms 29288 KB Output is correct
17 Correct 371 ms 29300 KB Output is correct
18 Correct 414 ms 29392 KB Output is correct
19 Correct 3186 ms 30216 KB Output is correct
20 Correct 4074 ms 30284 KB Output is correct
21 Correct 4527 ms 30336 KB Output is correct
22 Correct 4731 ms 30216 KB Output is correct
23 Correct 3652 ms 30244 KB Output is correct
24 Correct 3712 ms 30360 KB Output is correct
25 Correct 3827 ms 30184 KB Output is correct
26 Correct 3724 ms 30204 KB Output is correct
27 Correct 3714 ms 30144 KB Output is correct
28 Correct 3678 ms 30132 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3280 ms 30344 KB Output is correct
2 Execution timed out 9033 ms 31480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 29140 KB Output is correct
2 Correct 140 ms 29172 KB Output is correct
3 Correct 397 ms 29328 KB Output is correct
4 Correct 393 ms 29480 KB Output is correct
5 Correct 411 ms 29348 KB Output is correct
6 Correct 387 ms 29344 KB Output is correct
7 Correct 392 ms 29340 KB Output is correct
8 Correct 408 ms 29344 KB Output is correct
9 Correct 391 ms 29328 KB Output is correct
10 Correct 399 ms 29324 KB Output is correct
11 Correct 372 ms 29432 KB Output is correct
12 Correct 409 ms 29268 KB Output is correct
13 Correct 411 ms 29392 KB Output is correct
14 Correct 377 ms 29428 KB Output is correct
15 Correct 410 ms 29320 KB Output is correct
16 Correct 396 ms 29288 KB Output is correct
17 Correct 371 ms 29300 KB Output is correct
18 Correct 414 ms 29392 KB Output is correct
19 Correct 3186 ms 30216 KB Output is correct
20 Correct 4074 ms 30284 KB Output is correct
21 Correct 4527 ms 30336 KB Output is correct
22 Correct 4731 ms 30216 KB Output is correct
23 Correct 3652 ms 30244 KB Output is correct
24 Correct 3712 ms 30360 KB Output is correct
25 Correct 3827 ms 30184 KB Output is correct
26 Correct 3724 ms 30204 KB Output is correct
27 Correct 3714 ms 30144 KB Output is correct
28 Correct 3678 ms 30132 KB Output is correct
29 Correct 3280 ms 30344 KB Output is correct
30 Execution timed out 9033 ms 31480 KB Time limit exceeded
31 Halted 0 ms 0 KB -