Submission #160439

#	Time	Username	Problem	Language	Result	Execution time	Memory
160439		iefnah06	Bubble Sort 2 (JOI18_bubblesort2)	C++11	0 / 100	3807 ms	832 KiB

bubblesort2

#include "bubblesort2.h"

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;

const int MAXN = 2010;
int N, Q;
vector<int> A;

map<int, int> vals;

int bit[MAXN];
void update(int i, int v) {
	for (; i; i -= (i & -i)) {
		bit[i] = min(v, bit[i]);
	}
}
int query(int i) {
	int ans = INF;
	for (; i <= int(vals.size()); i += (i & -i)) {
		ans = min(ans, bit[i]);
	}
	return ans;
}

int query() {
	vals.clear();
	for (int i = 0; i < N; i++) {
		vals[A[i]] = 0;
	}
	int cur = 0;
	for (auto& it : vals) {
		it.second = ++cur;
	}

	for (int w = 1; w <= int(vals.size()); w++) {
		bit[w] = INF;
	}
	int ans = 0;
	for (int i = 0; i < N; i++) { // position of first number greater than i
		ans = max(ans, i - query(A[i]+1));
		update(A[i], i);
	}
	return ans;
}

std::vector<int> countScans(std::vector<int> a,std::vector<int> X,std::vector<int> V){
	A = a;
	N = int(a.size());
	Q = int(X.size());
	vector<int> answer(Q);
	for (int q = 0; q < Q; q++) {
		A[X[q]] = V[q];
		answer[q] = query();
	}
	return answer;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40