oj.uz

Submission #539131

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

constexpr int maxn = 5e5+10;

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;
	bit.clear();
	for(int i = 0; i < (int)A.size(); 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:33:25: warning: unused variable 'N' [-Wunused-variable]
   33 |  int Q = (int)X.size(), N = (int)A.size();
      |                         ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1820 ms 2624 KB Output is correct
2 Execution timed out 9085 ms 3332 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 4308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -