oj.uz

Submission #894666

# Submission time Handle Problem Language Result Execution time Memory
894666 2023-12-28T15:53:16 Z vovik Bubble Sort 2 (JOI18_bubblesort2) C++
100 / 100
 2275 ms 54608 KB 
#include <bits/stdc++.h>
 
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
 
struct node {
    std::pair<int, int> x;
    int y = rand();
    int L = 0, R = 0;
    int sz = 1;
    int cost = -1e9;
};
 
const int N = 1e6 + 5;
node t[N];
int cur = 0;
 
void pull(int v) {
    t[v].sz = t[t[v].L].sz + t[t[v].R].sz + 1;
    t[v].cost = std::max({t[t[v].L].cost, t[v].x.second - t[t[v].L].sz, t[t[v].R].cost - t[t[v].L].sz - 1});
}
 
int merge(int v, int u) {
    if (!v || !u) return v | u;
    if (t[v].y > t[u].y) return t[v].R = merge(t[v].R, u), pull(v), v;
    return t[u].L = merge(v, t[u].L), pull(u), u;
}
 
std::pair<int, int> split(int v, std::pair<int, int> x) {
    if (!v) return {v, v};
    if (t[v].x <= x) {
        auto [a, b] = split(t[v].R, x);
        return t[v].R = a, pull(v), std::pair<int, int>{v, b};
    }
    auto [a, b] = split(t[v].L, x);
    return t[v].L = b, pull(v), std::pair<int, int>{a, v};
}
 
void add(int&v, std::pair<int, int> x) {
    auto [a, b] = split(v, x);
    t[++cur].x = x;
    pull(cur);
    v = merge(merge(a, cur), b);
}
 
void del(int&v, std::pair<int, int> x) {
    auto [a, b] = split(v, x);
    auto [y, z] = split(a, {x.first, x.second - 1});
    v = merge(y, b);
}
 
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    t[0].sz = 0;
    std::vector<int> ans(X.size());
    int v = 0;
    for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
    for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
    return ans;
}
 
 
#ifdef __APPLE__
#include <cstdio>
#include <cstdlib>
#include <vector>
 
int readInt() {
    int i;
    if (scanf("%d", &i) != 1) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    return i;
}
 
int main() {
    int N, Q;
    N = readInt();
    Q = readInt();
 
    std::vector<int> A(N);
    for (int i = 0; i < N; i++)
        A[i] = readInt();
 
    std::vector<int> X(Q), V(Q);
    for (int j = 0; j < Q; j++) {
        X[j] = readInt();
        V[j] = readInt();
    }
 
    std::vector<int> res = countScans(A, X, V);
 
    for (int j = 0; j < int(res.size()); j++)
        printf("%d\n", res[j]);
}
#endif

Compilation message

bubblesort2.cpp: In function 'std::pair<int, int> split(int, std::pair<int, int>)':
bubblesort2.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [a, b] = split(t[v].R, x);
      |              ^
bubblesort2.cpp:34:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     auto [a, b] = split(t[v].L, x);
      |          ^
bubblesort2.cpp: In function 'void add(int&, std::pair<int, int>)':
bubblesort2.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [a, b] = split(v, x);
      |          ^
bubblesort2.cpp: In function 'void del(int&, std::pair<int, int>)':
bubblesort2.cpp:46:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     auto [a, b] = split(v, x);
      |          ^
bubblesort2.cpp:47:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     auto [y, z] = split(a, {x.first, x.second - 1});
      |          ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
      |                     ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27740 KB Output is correct
2 Correct 14 ms 27996 KB Output is correct
3 Correct 13 ms 27740 KB Output is correct
4 Correct 13 ms 27740 KB Output is correct
5 Correct 13 ms 27740 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 13 ms 27736 KB Output is correct
8 Correct 13 ms 27740 KB Output is correct
9 Correct 13 ms 27748 KB Output is correct
10 Correct 17 ms 27780 KB Output is correct
11 Correct 16 ms 27736 KB Output is correct
12 Correct 12 ms 27740 KB Output is correct
13 Correct 13 ms 27856 KB Output is correct
14 Correct 15 ms 28028 KB Output is correct
15 Correct 15 ms 27740 KB Output is correct
16 Correct 13 ms 27740 KB Output is correct
17 Correct 12 ms 27740 KB Output is correct
18 Correct 12 ms 27760 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27740 KB Output is correct
2 Correct 14 ms 27996 KB Output is correct
3 Correct 13 ms 27740 KB Output is correct
4 Correct 13 ms 27740 KB Output is correct
5 Correct 13 ms 27740 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 13 ms 27736 KB Output is correct
8 Correct 13 ms 27740 KB Output is correct
9 Correct 13 ms 27748 KB Output is correct
10 Correct 17 ms 27780 KB Output is correct
11 Correct 16 ms 27736 KB Output is correct
12 Correct 12 ms 27740 KB Output is correct
13 Correct 13 ms 27856 KB Output is correct
14 Correct 15 ms 28028 KB Output is correct
15 Correct 15 ms 27740 KB Output is correct
16 Correct 13 ms 27740 KB Output is correct
17 Correct 12 ms 27740 KB Output is correct
18 Correct 12 ms 27760 KB Output is correct
19 Correct 22 ms 27996 KB Output is correct
20 Correct 25 ms 28252 KB Output is correct
21 Correct 31 ms 28092 KB Output is correct
22 Correct 27 ms 28240 KB Output is correct
23 Correct 23 ms 27996 KB Output is correct
24 Correct 23 ms 28204 KB Output is correct
25 Correct 24 ms 28100 KB Output is correct
26 Correct 23 ms 28216 KB Output is correct
27 Correct 23 ms 28192 KB Output is correct
28 Correct 23 ms 28200 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28088 KB Output is correct
2 Correct 86 ms 28924 KB Output is correct
3 Correct 117 ms 29532 KB Output is correct
4 Correct 123 ms 29764 KB Output is correct
5 Correct 114 ms 29772 KB Output is correct
6 Correct 132 ms 29788 KB Output is correct
7 Correct 116 ms 29772 KB Output is correct
8 Correct 149 ms 29784 KB Output is correct
9 Correct 123 ms 29772 KB Output is correct
10 Correct 83 ms 29848 KB Output is correct
11 Correct 79 ms 29784 KB Output is correct
12 Correct 80 ms 29796 KB Output is correct
13 Correct 69 ms 29788 KB Output is correct
14 Correct 74 ms 29628 KB Output is correct
15 Correct 69 ms 29776 KB Output is correct
16 Correct 60 ms 29780 KB Output is correct
17 Correct 61 ms 29680 KB Output is correct
18 Correct 63 ms 29828 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 27740 KB Output is correct
2 Correct 14 ms 27996 KB Output is correct
3 Correct 13 ms 27740 KB Output is correct
4 Correct 13 ms 27740 KB Output is correct
5 Correct 13 ms 27740 KB Output is correct
6 Correct 13 ms 27740 KB Output is correct
7 Correct 13 ms 27736 KB Output is correct
8 Correct 13 ms 27740 KB Output is correct
9 Correct 13 ms 27748 KB Output is correct
10 Correct 17 ms 27780 KB Output is correct
11 Correct 16 ms 27736 KB Output is correct
12 Correct 12 ms 27740 KB Output is correct
13 Correct 13 ms 27856 KB Output is correct
14 Correct 15 ms 28028 KB Output is correct
15 Correct 15 ms 27740 KB Output is correct
16 Correct 13 ms 27740 KB Output is correct
17 Correct 12 ms 27740 KB Output is correct
18 Correct 12 ms 27760 KB Output is correct
19 Correct 22 ms 27996 KB Output is correct
20 Correct 25 ms 28252 KB Output is correct
21 Correct 31 ms 28092 KB Output is correct
22 Correct 27 ms 28240 KB Output is correct
23 Correct 23 ms 27996 KB Output is correct
24 Correct 23 ms 28204 KB Output is correct
25 Correct 24 ms 28100 KB Output is correct
26 Correct 23 ms 28216 KB Output is correct
27 Correct 23 ms 28192 KB Output is correct
28 Correct 23 ms 28200 KB Output is correct
29 Correct 28 ms 28088 KB Output is correct
30 Correct 86 ms 28924 KB Output is correct
31 Correct 117 ms 29532 KB Output is correct
32 Correct 123 ms 29764 KB Output is correct
33 Correct 114 ms 29772 KB Output is correct
34 Correct 132 ms 29788 KB Output is correct
35 Correct 116 ms 29772 KB Output is correct
36 Correct 149 ms 29784 KB Output is correct
37 Correct 123 ms 29772 KB Output is correct
38 Correct 83 ms 29848 KB Output is correct
39 Correct 79 ms 29784 KB Output is correct
40 Correct 80 ms 29796 KB Output is correct
41 Correct 69 ms 29788 KB Output is correct
42 Correct 74 ms 29628 KB Output is correct
43 Correct 69 ms 29776 KB Output is correct
44 Correct 60 ms 29780 KB Output is correct
45 Correct 61 ms 29680 KB Output is correct
46 Correct 63 ms 29828 KB Output is correct
47 Correct 426 ms 35484 KB Output is correct
48 Correct 1781 ms 52504 KB Output is correct
49 Correct 2045 ms 54396 KB Output is correct
50 Correct 2035 ms 54404 KB Output is correct
51 Correct 2275 ms 54400 KB Output is correct
52 Correct 2104 ms 54400 KB Output is correct
53 Correct 2231 ms 54396 KB Output is correct
54 Correct 1980 ms 54420 KB Output is correct
55 Correct 2151 ms 54584 KB Output is correct
56 Correct 1900 ms 54544 KB Output is correct
57 Correct 2092 ms 54608 KB Output is correct
58 Correct 1857 ms 54544 KB Output is correct
59 Correct 1688 ms 53220 KB Output is correct
60 Correct 1661 ms 53220 KB Output is correct
61 Correct 1767 ms 53220 KB Output is correct
62 Correct 1657 ms 53072 KB Output is correct
63 Correct 1744 ms 53084 KB Output is correct
64 Correct 1657 ms 53076 KB Output is correct
65 Correct 1530 ms 53140 KB Output is correct
66 Correct 1544 ms 52940 KB Output is correct
67 Correct 1509 ms 52936 KB Output is correct