| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 539135 | 2022-03-18T13:05:35 Z | LucaDantas | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 9000 ms | 5356 KB |
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
constexpr int maxn = 1e6+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;
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();
map<int,int> mp;
for(int x : A)
mp[x] = 0;
for(int x : V)
mp[x] = 0;
int coord = 0;
for(auto& it : mp)
it.second = ++coord;
for(int& x : A)
x = mp[x];
for(int& x : V)
x = mp[x];
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 66 ms | 4180 KB | Output is correct |
| 2 | Correct | 144 ms | 4308 KB | Output is correct |
| 3 | Correct | 365 ms | 4436 KB | Output is correct |
| 4 | Correct | 387 ms | 4444 KB | Output is correct |
| 5 | Correct | 343 ms | 4436 KB | Output is correct |
| 6 | Correct | 322 ms | 4436 KB | Output is correct |
| 7 | Correct | 333 ms | 4436 KB | Output is correct |
| 8 | Correct | 354 ms | 4436 KB | Output is correct |
| 9 | Correct | 348 ms | 4436 KB | Output is correct |
| 10 | Correct | 371 ms | 4408 KB | Output is correct |
| 11 | Correct | 351 ms | 4428 KB | Output is correct |
| 12 | Correct | 349 ms | 4412 KB | Output is correct |
| 13 | Correct | 363 ms | 4400 KB | Output is correct |
| 14 | Correct | 340 ms | 4404 KB | Output is correct |
| 15 | Correct | 350 ms | 4396 KB | Output is correct |
| 16 | Correct | 337 ms | 4384 KB | Output is correct |
| 17 | Correct | 376 ms | 4392 KB | Output is correct |
| 18 | Correct | 330 ms | 4388 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 66 ms | 4180 KB | Output is correct |
| 2 | Correct | 144 ms | 4308 KB | Output is correct |
| 3 | Correct | 365 ms | 4436 KB | Output is correct |
| 4 | Correct | 387 ms | 4444 KB | Output is correct |
| 5 | Correct | 343 ms | 4436 KB | Output is correct |
| 6 | Correct | 322 ms | 4436 KB | Output is correct |
| 7 | Correct | 333 ms | 4436 KB | Output is correct |
| 8 | Correct | 354 ms | 4436 KB | Output is correct |
| 9 | Correct | 348 ms | 4436 KB | Output is correct |
| 10 | Correct | 371 ms | 4408 KB | Output is correct |
| 11 | Correct | 351 ms | 4428 KB | Output is correct |
| 12 | Correct | 349 ms | 4412 KB | Output is correct |
| 13 | Correct | 363 ms | 4400 KB | Output is correct |
| 14 | Correct | 340 ms | 4404 KB | Output is correct |
| 15 | Correct | 350 ms | 4396 KB | Output is correct |
| 16 | Correct | 337 ms | 4384 KB | Output is correct |
| 17 | Correct | 376 ms | 4392 KB | Output is correct |
| 18 | Correct | 330 ms | 4388 KB | Output is correct |
| 19 | Correct | 2491 ms | 5040 KB | Output is correct |
| 20 | Correct | 3157 ms | 5352 KB | Output is correct |
| 21 | Correct | 2837 ms | 5356 KB | Output is correct |
| 22 | Correct | 2633 ms | 5356 KB | Output is correct |
| 23 | Correct | 2567 ms | 5232 KB | Output is correct |
| 24 | Correct | 2516 ms | 5232 KB | Output is correct |
| 25 | Correct | 2525 ms | 5180 KB | Output is correct |
| 26 | Correct | 2514 ms | 5184 KB | Output is correct |
| 27 | Correct | 2536 ms | 5132 KB | Output is correct |
| 28 | Correct | 2539 ms | 5124 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1888 ms | 4448 KB | Output is correct |
| 2 | Execution timed out | 9004 ms | 4984 KB | Time limit exceeded |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 66 ms | 4180 KB | Output is correct |
| 2 | Correct | 144 ms | 4308 KB | Output is correct |
| 3 | Correct | 365 ms | 4436 KB | Output is correct |
| 4 | Correct | 387 ms | 4444 KB | Output is correct |
| 5 | Correct | 343 ms | 4436 KB | Output is correct |
| 6 | Correct | 322 ms | 4436 KB | Output is correct |
| 7 | Correct | 333 ms | 4436 KB | Output is correct |
| 8 | Correct | 354 ms | 4436 KB | Output is correct |
| 9 | Correct | 348 ms | 4436 KB | Output is correct |
| 10 | Correct | 371 ms | 4408 KB | Output is correct |
| 11 | Correct | 351 ms | 4428 KB | Output is correct |
| 12 | Correct | 349 ms | 4412 KB | Output is correct |
| 13 | Correct | 363 ms | 4400 KB | Output is correct |
| 14 | Correct | 340 ms | 4404 KB | Output is correct |
| 15 | Correct | 350 ms | 4396 KB | Output is correct |
| 16 | Correct | 337 ms | 4384 KB | Output is correct |
| 17 | Correct | 376 ms | 4392 KB | Output is correct |
| 18 | Correct | 330 ms | 4388 KB | Output is correct |
| 19 | Correct | 2491 ms | 5040 KB | Output is correct |
| 20 | Correct | 3157 ms | 5352 KB | Output is correct |
| 21 | Correct | 2837 ms | 5356 KB | Output is correct |
| 22 | Correct | 2633 ms | 5356 KB | Output is correct |
| 23 | Correct | 2567 ms | 5232 KB | Output is correct |
| 24 | Correct | 2516 ms | 5232 KB | Output is correct |
| 25 | Correct | 2525 ms | 5180 KB | Output is correct |
| 26 | Correct | 2514 ms | 5184 KB | Output is correct |
| 27 | Correct | 2536 ms | 5132 KB | Output is correct |
| 28 | Correct | 2539 ms | 5124 KB | Output is correct |
| 29 | Correct | 1888 ms | 4448 KB | Output is correct |
| 30 | Execution timed out | 9004 ms | 4984 KB | Time limit exceeded |
| 31 | Halted | 0 ms | 0 KB | - |