oj.uz

Submission #526612

# Submission time Handle Problem Language Result Execution time Memory
526612 2022-02-15T15:13:42 Z Monarchuwu Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 8432 KB 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;

const int N = 5e5 + 5;
int n, q;
int a[N];

int b[N];
void update(int p, int old_val, int new_val) {
    b[p] = 0;
    for (int i = 0; i < p; ++i) b[p] += a[i] > new_val;
    for (int i = p + 1; i < n; ++i) {
        b[i] -= old_val > a[i];
        b[i] += new_val > a[i];
    }
}
int query() { return *max_element(b, b + n); }

vector<int> countScans(vector<int> A, vector<int> x, vector<int> v) {
    n = A.size(), q = x.size();
    for (int i = 0; i < n; ++i) update(i, 0, a[i] = A[i]);

    vector<int> ans;
    for (int i = 0; i < q; ++i) {
        update(x[i], a[x[i]], v[i]);
        a[x[i]] = v[i];
        ans.push_back(query());
    }
    return ans;
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 13 ms 336 KB Output is correct
4 Correct 13 ms 448 KB Output is correct
5 Correct 12 ms 368 KB Output is correct
6 Correct 13 ms 372 KB Output is correct
7 Correct 13 ms 368 KB Output is correct
8 Correct 13 ms 344 KB Output is correct
9 Correct 16 ms 436 KB Output is correct
10 Correct 15 ms 440 KB Output is correct
11 Correct 15 ms 348 KB Output is correct
12 Correct 14 ms 404 KB Output is correct
13 Correct 14 ms 420 KB Output is correct
14 Correct 13 ms 344 KB Output is correct
15 Correct 12 ms 444 KB Output is correct
16 Correct 12 ms 440 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 14 ms 436 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 13 ms 336 KB Output is correct
4 Correct 13 ms 448 KB Output is correct
5 Correct 12 ms 368 KB Output is correct
6 Correct 13 ms 372 KB Output is correct
7 Correct 13 ms 368 KB Output is correct
8 Correct 13 ms 344 KB Output is correct
9 Correct 16 ms 436 KB Output is correct
10 Correct 15 ms 440 KB Output is correct
11 Correct 15 ms 348 KB Output is correct
12 Correct 14 ms 404 KB Output is correct
13 Correct 14 ms 420 KB Output is correct
14 Correct 13 ms 344 KB Output is correct
15 Correct 12 ms 444 KB Output is correct
16 Correct 12 ms 440 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 14 ms 436 KB Output is correct
19 Correct 151 ms 716 KB Output is correct
20 Correct 199 ms 844 KB Output is correct
21 Correct 191 ms 828 KB Output is correct
22 Correct 192 ms 804 KB Output is correct
23 Correct 233 ms 796 KB Output is correct
24 Correct 187 ms 768 KB Output is correct
25 Correct 193 ms 692 KB Output is correct
26 Correct 189 ms 872 KB Output is correct
27 Correct 197 ms 748 KB Output is correct
28 Correct 203 ms 688 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 884 KB Output is correct
2 Correct 3703 ms 1892 KB Output is correct
3 Correct 7402 ms 2816 KB Output is correct
4 Correct 7559 ms 2728 KB Output is correct
5 Correct 7520 ms 2796 KB Output is correct
6 Correct 7507 ms 2780 KB Output is correct
7 Correct 7351 ms 2736 KB Output is correct
8 Correct 7325 ms 2908 KB Output is correct
9 Correct 7476 ms 2804 KB Output is correct
10 Correct 6987 ms 2956 KB Output is correct
11 Correct 7069 ms 3124 KB Output is correct
12 Correct 6873 ms 2992 KB Output is correct
13 Correct 6774 ms 3016 KB Output is correct
14 Correct 6955 ms 3024 KB Output is correct
15 Correct 6727 ms 2784 KB Output is correct
16 Correct 6469 ms 2932 KB Output is correct
17 Correct 6533 ms 2876 KB Output is correct
18 Correct 6500 ms 2952 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 13 ms 336 KB Output is correct
4 Correct 13 ms 448 KB Output is correct
5 Correct 12 ms 368 KB Output is correct
6 Correct 13 ms 372 KB Output is correct
7 Correct 13 ms 368 KB Output is correct
8 Correct 13 ms 344 KB Output is correct
9 Correct 16 ms 436 KB Output is correct
10 Correct 15 ms 440 KB Output is correct
11 Correct 15 ms 348 KB Output is correct
12 Correct 14 ms 404 KB Output is correct
13 Correct 14 ms 420 KB Output is correct
14 Correct 13 ms 344 KB Output is correct
15 Correct 12 ms 444 KB Output is correct
16 Correct 12 ms 440 KB Output is correct
17 Correct 14 ms 344 KB Output is correct
18 Correct 14 ms 436 KB Output is correct
19 Correct 151 ms 716 KB Output is correct
20 Correct 199 ms 844 KB Output is correct
21 Correct 191 ms 828 KB Output is correct
22 Correct 192 ms 804 KB Output is correct
23 Correct 233 ms 796 KB Output is correct
24 Correct 187 ms 768 KB Output is correct
25 Correct 193 ms 692 KB Output is correct
26 Correct 189 ms 872 KB Output is correct
27 Correct 197 ms 748 KB Output is correct
28 Correct 203 ms 688 KB Output is correct
29 Correct 855 ms 884 KB Output is correct
30 Correct 3703 ms 1892 KB Output is correct
31 Correct 7402 ms 2816 KB Output is correct
32 Correct 7559 ms 2728 KB Output is correct
33 Correct 7520 ms 2796 KB Output is correct
34 Correct 7507 ms 2780 KB Output is correct
35 Correct 7351 ms 2736 KB Output is correct
36 Correct 7325 ms 2908 KB Output is correct
37 Correct 7476 ms 2804 KB Output is correct
38 Correct 6987 ms 2956 KB Output is correct
39 Correct 7069 ms 3124 KB Output is correct
40 Correct 6873 ms 2992 KB Output is correct
41 Correct 6774 ms 3016 KB Output is correct
42 Correct 6955 ms 3024 KB Output is correct
43 Correct 6727 ms 2784 KB Output is correct
44 Correct 6469 ms 2932 KB Output is correct
45 Correct 6533 ms 2876 KB Output is correct
46 Correct 6500 ms 2952 KB Output is correct
47 Execution timed out 9004 ms 8432 KB Time limit exceeded
48 Halted 0 ms 0 KB -