oj.uz

Submission #160449

# Submission time Handle Problem Language Result Execution time Memory
160449 2019-10-27T14:04:17 Z iefnah06 Bubble Sort 2 (JOI18_bubblesort2) C++11
17 / 100
 9000 ms 1784 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] += v;
	}
}
int query(int i) {
	int ans = 0;
	for (; i <= int(vals.size()); i += (i & -i)) {
		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] = 0;
	}
	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, query(v+1));
		update(v, 1);
	}
	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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 376 KB Output is correct
2 Correct 190 ms 448 KB Output is correct
3 Correct 1249 ms 504 KB Output is correct
4 Correct 1240 ms 632 KB Output is correct
5 Correct 1194 ms 564 KB Output is correct
6 Correct 1206 ms 568 KB Output is correct
7 Correct 1101 ms 568 KB Output is correct
8 Correct 1149 ms 564 KB Output is correct
9 Correct 1189 ms 564 KB Output is correct
10 Correct 1012 ms 556 KB Output is correct
11 Correct 1002 ms 564 KB Output is correct
12 Correct 1078 ms 556 KB Output is correct
13 Correct 1020 ms 556 KB Output is correct
14 Correct 1031 ms 556 KB Output is correct
15 Correct 1010 ms 632 KB Output is correct
16 Correct 997 ms 632 KB Output is correct
17 Correct 1020 ms 632 KB Output is correct
18 Correct 1062 ms 596 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 376 KB Output is correct
2 Correct 190 ms 448 KB Output is correct
3 Correct 1249 ms 504 KB Output is correct
4 Correct 1240 ms 632 KB Output is correct
5 Correct 1194 ms 564 KB Output is correct
6 Correct 1206 ms 568 KB Output is correct
7 Correct 1101 ms 568 KB Output is correct
8 Correct 1149 ms 564 KB Output is correct
9 Correct 1189 ms 564 KB Output is correct
10 Correct 1012 ms 556 KB Output is correct
11 Correct 1002 ms 564 KB Output is correct
12 Correct 1078 ms 556 KB Output is correct
13 Correct 1020 ms 556 KB Output is correct
14 Correct 1031 ms 556 KB Output is correct
15 Correct 1010 ms 632 KB Output is correct
16 Correct 997 ms 632 KB Output is correct
17 Correct 1020 ms 632 KB Output is correct
18 Correct 1062 ms 596 KB Output is correct
19 Runtime error 9 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6009 ms 836 KB Output is correct
2 Execution timed out 9009 ms 1656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 376 KB Output is correct
2 Correct 190 ms 448 KB Output is correct
3 Correct 1249 ms 504 KB Output is correct
4 Correct 1240 ms 632 KB Output is correct
5 Correct 1194 ms 564 KB Output is correct
6 Correct 1206 ms 568 KB Output is correct
7 Correct 1101 ms 568 KB Output is correct
8 Correct 1149 ms 564 KB Output is correct
9 Correct 1189 ms 564 KB Output is correct
10 Correct 1012 ms 556 KB Output is correct
11 Correct 1002 ms 564 KB Output is correct
12 Correct 1078 ms 556 KB Output is correct
13 Correct 1020 ms 556 KB Output is correct
14 Correct 1031 ms 556 KB Output is correct
15 Correct 1010 ms 632 KB Output is correct
16 Correct 997 ms 632 KB Output is correct
17 Correct 1020 ms 632 KB Output is correct
18 Correct 1062 ms 596 KB Output is correct
19 Runtime error 9 ms 1784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -