oj.uz

Submission #160442

# Submission time Handle Problem Language Result Execution time Memory
160442 2019-10-27T13:58:59 Z iefnah06 Bubble Sort 2 (JOI18_bubblesort2) C++11
0 / 100
 6466 ms 836 KB 
#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
		int v = vals[A[i]];
		ans = max(ans, i - query(v+1));
		update(v, 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 6466 ms 836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -