oj.uz

Submission #539181

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

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];
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(A[i] == -1) continue;
		while(pareto.size() && A[i] <= A[pareto.back()])
			pareto.pop_back();
		pareto.push_back(i);
	}

	/* puts("PARETO");
	for(int x : pareto)
		printf("%d ", x);
	puts(""); */

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

			// printf("%d %d -> %d\n", i, val, ans[id]);
		}

		if(A[i] != -1) 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++) {
		A[X[q]] = -1;
		qr[X[q]] = {{V[q], q}};
		rebuild(A);
		A[X[q]] = V[q];

		int last = bs(V[q], A);
		// printf("%d %d -> %d\n", X[q], V[q], last);

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

		answer[q] = max(seg.query(), ans[q]);
	}
	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29140 KB Output is correct
2 Correct 137 ms 29180 KB Output is correct
3 Correct 387 ms 29368 KB Output is correct
4 Correct 388 ms 29268 KB Output is correct
5 Correct 384 ms 29368 KB Output is correct
6 Correct 374 ms 29368 KB Output is correct
7 Correct 373 ms 29364 KB Output is correct
8 Correct 390 ms 29420 KB Output is correct
9 Correct 390 ms 29496 KB Output is correct
10 Correct 366 ms 29452 KB Output is correct
11 Correct 397 ms 29452 KB Output is correct
12 Correct 363 ms 29328 KB Output is correct
13 Correct 368 ms 29320 KB Output is correct
14 Correct 368 ms 29328 KB Output is correct
15 Correct 362 ms 29260 KB Output is correct
16 Correct 371 ms 29308 KB Output is correct
17 Correct 362 ms 29316 KB Output is correct
18 Correct 364 ms 29316 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29140 KB Output is correct
2 Correct 137 ms 29180 KB Output is correct
3 Correct 387 ms 29368 KB Output is correct
4 Correct 388 ms 29268 KB Output is correct
5 Correct 384 ms 29368 KB Output is correct
6 Correct 374 ms 29368 KB Output is correct
7 Correct 373 ms 29364 KB Output is correct
8 Correct 390 ms 29420 KB Output is correct
9 Correct 390 ms 29496 KB Output is correct
10 Correct 366 ms 29452 KB Output is correct
11 Correct 397 ms 29452 KB Output is correct
12 Correct 363 ms 29328 KB Output is correct
13 Correct 368 ms 29320 KB Output is correct
14 Correct 368 ms 29328 KB Output is correct
15 Correct 362 ms 29260 KB Output is correct
16 Correct 371 ms 29308 KB Output is correct
17 Correct 362 ms 29316 KB Output is correct
18 Correct 364 ms 29316 KB Output is correct
19 Correct 3024 ms 30572 KB Output is correct
20 Correct 3868 ms 30452 KB Output is correct
21 Correct 3556 ms 30588 KB Output is correct
22 Correct 3805 ms 30476 KB Output is correct
23 Correct 3468 ms 30192 KB Output is correct
24 Correct 3690 ms 30204 KB Output is correct
25 Correct 3472 ms 30192 KB Output is correct
26 Correct 3441 ms 30320 KB Output is correct
27 Correct 3408 ms 30124 KB Output is correct
28 Correct 3488 ms 30116 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3065 ms 30040 KB Output is correct
2 Execution timed out 9073 ms 31456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29140 KB Output is correct
2 Correct 137 ms 29180 KB Output is correct
3 Correct 387 ms 29368 KB Output is correct
4 Correct 388 ms 29268 KB Output is correct
5 Correct 384 ms 29368 KB Output is correct
6 Correct 374 ms 29368 KB Output is correct
7 Correct 373 ms 29364 KB Output is correct
8 Correct 390 ms 29420 KB Output is correct
9 Correct 390 ms 29496 KB Output is correct
10 Correct 366 ms 29452 KB Output is correct
11 Correct 397 ms 29452 KB Output is correct
12 Correct 363 ms 29328 KB Output is correct
13 Correct 368 ms 29320 KB Output is correct
14 Correct 368 ms 29328 KB Output is correct
15 Correct 362 ms 29260 KB Output is correct
16 Correct 371 ms 29308 KB Output is correct
17 Correct 362 ms 29316 KB Output is correct
18 Correct 364 ms 29316 KB Output is correct
19 Correct 3024 ms 30572 KB Output is correct
20 Correct 3868 ms 30452 KB Output is correct
21 Correct 3556 ms 30588 KB Output is correct
22 Correct 3805 ms 30476 KB Output is correct
23 Correct 3468 ms 30192 KB Output is correct
24 Correct 3690 ms 30204 KB Output is correct
25 Correct 3472 ms 30192 KB Output is correct
26 Correct 3441 ms 30320 KB Output is correct
27 Correct 3408 ms 30124 KB Output is correct
28 Correct 3488 ms 30116 KB Output is correct
29 Correct 3065 ms 30040 KB Output is correct
30 Execution timed out 9073 ms 31456 KB Time limit exceeded
31 Halted 0 ms 0 KB -