oj.uz

Submission #539132

# Submission time Handle Problem Language Result Execution time Memory
539132 2022-03-18T13:02:32 Z LucaDantas Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 800 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

constexpr int maxn = 2000+10; // subtasks brutao, mudar

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;

// fazer o brutao pra checar se essa ideia ta certo e se eu codo ela pra full

int calc(const vector<int>& A) {
	int ans = 0;
	vector<int> foi;
	// bit.clear();
	for(int i = 0; i < (int)A.size(); i++) {
		int aq = 0;
		for(int x : foi)
			aq += x > A[i];
		ans = max(ans, aq);
		foi.push_back(A[i]);
		// ans = max(ans, bit.query(A[i]+1)), bit.upd(A[i], 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();
	std::vector<int> answer(Q);
	for(int q = 0; q < Q; q++) {
		A[X[q]] = V[q];
		answer[q] = calc(A);
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:40:25: warning: unused variable 'N' [-Wunused-variable]
   40 |  int Q = (int)X.size(), N = (int)A.size();
      |                         ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 308 KB Output is correct
2 Correct 235 ms 332 KB Output is correct
3 Correct 3358 ms 400 KB Output is correct
4 Correct 3232 ms 400 KB Output is correct
5 Correct 3404 ms 396 KB Output is correct
6 Correct 3185 ms 400 KB Output is correct
7 Correct 3056 ms 400 KB Output is correct
8 Correct 2938 ms 400 KB Output is correct
9 Correct 3188 ms 396 KB Output is correct
10 Correct 3285 ms 392 KB Output is correct
11 Correct 3340 ms 392 KB Output is correct
12 Correct 3305 ms 392 KB Output is correct
13 Correct 3387 ms 388 KB Output is correct
14 Correct 3311 ms 392 KB Output is correct
15 Correct 3471 ms 396 KB Output is correct
16 Correct 3570 ms 392 KB Output is correct
17 Correct 3156 ms 392 KB Output is correct
18 Correct 3388 ms 392 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 308 KB Output is correct
2 Correct 235 ms 332 KB Output is correct
3 Correct 3358 ms 400 KB Output is correct
4 Correct 3232 ms 400 KB Output is correct
5 Correct 3404 ms 396 KB Output is correct
6 Correct 3185 ms 400 KB Output is correct
7 Correct 3056 ms 400 KB Output is correct
8 Correct 2938 ms 400 KB Output is correct
9 Correct 3188 ms 396 KB Output is correct
10 Correct 3285 ms 392 KB Output is correct
11 Correct 3340 ms 392 KB Output is correct
12 Correct 3305 ms 392 KB Output is correct
13 Correct 3387 ms 388 KB Output is correct
14 Correct 3311 ms 392 KB Output is correct
15 Correct 3471 ms 396 KB Output is correct
16 Correct 3570 ms 392 KB Output is correct
17 Correct 3156 ms 392 KB Output is correct
18 Correct 3388 ms 392 KB Output is correct
19 Execution timed out 9075 ms 736 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9053 ms 800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 308 KB Output is correct
2 Correct 235 ms 332 KB Output is correct
3 Correct 3358 ms 400 KB Output is correct
4 Correct 3232 ms 400 KB Output is correct
5 Correct 3404 ms 396 KB Output is correct
6 Correct 3185 ms 400 KB Output is correct
7 Correct 3056 ms 400 KB Output is correct
8 Correct 2938 ms 400 KB Output is correct
9 Correct 3188 ms 396 KB Output is correct
10 Correct 3285 ms 392 KB Output is correct
11 Correct 3340 ms 392 KB Output is correct
12 Correct 3305 ms 392 KB Output is correct
13 Correct 3387 ms 388 KB Output is correct
14 Correct 3311 ms 392 KB Output is correct
15 Correct 3471 ms 396 KB Output is correct
16 Correct 3570 ms 392 KB Output is correct
17 Correct 3156 ms 392 KB Output is correct
18 Correct 3388 ms 392 KB Output is correct
19 Execution timed out 9075 ms 736 KB Time limit exceeded
20 Halted 0 ms 0 KB -