Submission #381831

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381831	2021-03-26T03:30:04 Z	JerryLiu06	Bubble Sort 2 (JOI18_bubblesort2)	C++11	60 / 100	844 ms	49948 KB

bubblesort2

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define pb push_back

#define f first
#define s second

int N, Q, MX; pii tree[2000010]; vector<pii> allX; const int INF = 1000000000;

int getX(pii P) { return lower_bound(allX.begin(), allX.end(), P) - allX.begin() + 1; }

void pushdown(int x, int l, int r) {
    tree[x].f += tree[x].s; if (l < r) { tree[2 * x].s += tree[x].s; tree[2 * x + 1].s += tree[x].s; } tree[x].s = 0;
}
void updRange(int x, int l, int r, int tl, int tr, int C) { int mid = (l + r) / 2;
    pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { tree[x].s += C; return ; }

    updRange(2 * x, l, mid, tl, tr, C); updRange(2 * x + 1, mid + 1, r, tl, tr, C);

    pushdown(2 * x, l, mid); pushdown(2 * x + 1, mid + 1, r); tree[x].f = max(tree[2 * x].f, tree[2 * x + 1].f);
}
void INSERT(pii P) { int X = getX(P); updRange(1, 1, MX, X, X, INF + P.s); updRange(1, 1, MX, X + 1, MX, -1); }
void REMOVE(pii P) { int X = getX(P); updRange(1, 1, MX, X, X, -INF - P.s); updRange(1, 1, MX, X + 1, MX, 1); }

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) { int N = A.size(); int Q = X.size();
    for (int i = 0; i < N; i++) allX.pb(pii {A[i], i}); for (int i = 0; i < Q; i++) allX.pb(pii {V[i], X[i]});

    sort(allX.begin(), allX.end()); allX.resize(distance(allX.begin(), unique(allX.begin(), allX.end())));

    MX = allX.size(); updRange(1, 1, MX, 1, MX, -INF);

    for (int i = 0; i < N; i++) INSERT(pii {A[i], i});

    vector<int> res; for (int i = 0; i < Q; i++) {
        REMOVE(pii {A[X[i]], X[i]}); INSERT(pii {V[i], X[i]});

        A[X[i]] = V[i]; res.pb(tree[1].f);
    }
    return res;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:30:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   30 |     for (int i = 0; i < N; i++) allX.pb(pii {A[i], i}); for (int i = 0; i < Q; i++) allX.pb(pii {V[i], X[i]});
      |     ^~~
bubblesort2.cpp:30:57: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   30 |     for (int i = 0; i < N; i++) allX.pb(pii {A[i], i}); for (int i = 0; i < Q; i++) allX.pb(pii {V[i], X[i]});
      |                                                         ^~~

Subtask #1
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	3 ms	364 KB	Output is correct
3	Correct	7 ms	620 KB	Output is correct
4	Correct	7 ms	620 KB	Output is correct
5	Correct	7 ms	620 KB	Output is correct
6	Correct	7 ms	620 KB	Output is correct
7	Correct	7 ms	512 KB	Output is correct
8	Correct	7 ms	620 KB	Output is correct
9	Correct	7 ms	620 KB	Output is correct
10	Correct	7 ms	620 KB	Output is correct
11	Correct	7 ms	620 KB	Output is correct
12	Correct	7 ms	620 KB	Output is correct
13	Correct	8 ms	764 KB	Output is correct
14	Correct	7 ms	620 KB	Output is correct
15	Correct	8 ms	620 KB	Output is correct
16	Correct	6 ms	620 KB	Output is correct
17	Correct	7 ms	620 KB	Output is correct
18	Correct	7 ms	620 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	3 ms	364 KB	Output is correct
3	Correct	7 ms	620 KB	Output is correct
4	Correct	7 ms	620 KB	Output is correct
5	Correct	7 ms	620 KB	Output is correct
6	Correct	7 ms	620 KB	Output is correct
7	Correct	7 ms	512 KB	Output is correct
8	Correct	7 ms	620 KB	Output is correct
9	Correct	7 ms	620 KB	Output is correct
10	Correct	7 ms	620 KB	Output is correct
11	Correct	7 ms	620 KB	Output is correct
12	Correct	7 ms	620 KB	Output is correct
13	Correct	8 ms	764 KB	Output is correct
14	Correct	7 ms	620 KB	Output is correct
15	Correct	8 ms	620 KB	Output is correct
16	Correct	6 ms	620 KB	Output is correct
17	Correct	7 ms	620 KB	Output is correct
18	Correct	7 ms	620 KB	Output is correct
19	Correct	25 ms	1260 KB	Output is correct
20	Correct	28 ms	1260 KB	Output is correct
21	Correct	27 ms	1260 KB	Output is correct
22	Correct	29 ms	1260 KB	Output is correct
23	Correct	28 ms	1260 KB	Output is correct
24	Correct	29 ms	1260 KB	Output is correct
25	Correct	26 ms	1260 KB	Output is correct
26	Correct	27 ms	1260 KB	Output is correct
27	Correct	26 ms	1260 KB	Output is correct
28	Correct	26 ms	1260 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	1512 KB	Output is correct
2	Correct	117 ms	2788 KB	Output is correct
3	Correct	213 ms	4832 KB	Output is correct
4	Correct	215 ms	5600 KB	Output is correct
5	Correct	228 ms	5344 KB	Output is correct
6	Correct	217 ms	5344 KB	Output is correct
7	Correct	217 ms	5428 KB	Output is correct
8	Correct	214 ms	5420 KB	Output is correct
9	Correct	215 ms	5344 KB	Output is correct
10	Correct	181 ms	4448 KB	Output is correct
11	Correct	177 ms	4448 KB	Output is correct
12	Correct	173 ms	4448 KB	Output is correct
13	Correct	184 ms	4496 KB	Output is correct
14	Correct	175 ms	4448 KB	Output is correct
15	Correct	174 ms	4448 KB	Output is correct
16	Correct	165 ms	4448 KB	Output is correct
17	Correct	171 ms	4448 KB	Output is correct
18	Correct	173 ms	4448 KB	Output is correct

Subtask #4
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	3 ms	364 KB	Output is correct
3	Correct	7 ms	620 KB	Output is correct
4	Correct	7 ms	620 KB	Output is correct
5	Correct	7 ms	620 KB	Output is correct
6	Correct	7 ms	620 KB	Output is correct
7	Correct	7 ms	512 KB	Output is correct
8	Correct	7 ms	620 KB	Output is correct
9	Correct	7 ms	620 KB	Output is correct
10	Correct	7 ms	620 KB	Output is correct
11	Correct	7 ms	620 KB	Output is correct
12	Correct	7 ms	620 KB	Output is correct
13	Correct	8 ms	764 KB	Output is correct
14	Correct	7 ms	620 KB	Output is correct
15	Correct	8 ms	620 KB	Output is correct
16	Correct	6 ms	620 KB	Output is correct
17	Correct	7 ms	620 KB	Output is correct
18	Correct	7 ms	620 KB	Output is correct
19	Correct	25 ms	1260 KB	Output is correct
20	Correct	28 ms	1260 KB	Output is correct
21	Correct	27 ms	1260 KB	Output is correct
22	Correct	29 ms	1260 KB	Output is correct
23	Correct	28 ms	1260 KB	Output is correct
24	Correct	29 ms	1260 KB	Output is correct
25	Correct	26 ms	1260 KB	Output is correct
26	Correct	27 ms	1260 KB	Output is correct
27	Correct	26 ms	1260 KB	Output is correct
28	Correct	26 ms	1260 KB	Output is correct
29	Correct	39 ms	1512 KB	Output is correct
30	Correct	117 ms	2788 KB	Output is correct
31	Correct	213 ms	4832 KB	Output is correct
32	Correct	215 ms	5600 KB	Output is correct
33	Correct	228 ms	5344 KB	Output is correct
34	Correct	217 ms	5344 KB	Output is correct
35	Correct	217 ms	5428 KB	Output is correct
36	Correct	214 ms	5420 KB	Output is correct
37	Correct	215 ms	5344 KB	Output is correct
38	Correct	181 ms	4448 KB	Output is correct
39	Correct	177 ms	4448 KB	Output is correct
40	Correct	173 ms	4448 KB	Output is correct
41	Correct	184 ms	4496 KB	Output is correct
42	Correct	175 ms	4448 KB	Output is correct
43	Correct	174 ms	4448 KB	Output is correct
44	Correct	165 ms	4448 KB	Output is correct
45	Correct	171 ms	4448 KB	Output is correct
46	Correct	173 ms	4448 KB	Output is correct
47	Correct	844 ms	19544 KB	Output is correct
48	Runtime error	365 ms	49948 KB	Execution killed with signal 11
49	Halted	0 ms	0 KB	-

Submission #381831

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 40.0