답안 #67538 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67538	2018-08-14T19:11:41 Z	imeimi2000	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2773 ms	42908 KB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pii;

int n, q, k;
pii comp[1000000];
const int inf = 1e8;
int seg[1 << 21];
int lay[1 << 21];
int fen[1000001];

void updatePoint(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i] = v;
        lay[i] = 0;
        return;
    }
    
    seg[i << 1] += lay[i];
    seg[i << 1 | 1] += lay[i];
    lay[i << 1] += lay[i];
    lay[i << 1 | 1] += lay[i];
    lay[i] = 0;
    
    int m = (s + e) / 2;
    if (x <= m) updatePoint(i << 1, s, m, x, v);
    else updatePoint(i << 1 | 1, m + 1, e, x, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}

void updateRange(int i, int s, int e, int x, int y, int v) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        seg[i] += v;
        lay[i] += v;
        return;
    }
    int m = (s + e) / 2;
    updateRange(i << 1, s, m, x, y, v);
    updateRange(i << 1 | 1, m + 1, e, x, y, v);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}

void update(int i, int x) {
    while (i <= k) {
        fen[i] += x;
        i += i & -i;
    }
}

int query(int i) {
    int ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

int find(int i, int x) {
    return lower_bound(comp, comp + k, pii(x, i)) - comp + 1;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    for (int i = 0; i < (1 << 21); ++i) seg[i] = lay[i] = -inf;
	n = A.size();
	q = X.size();
	for (int i = 0; i < n; ++i) comp[k++] = pii(A[i], i);
	for (int i = 0; i < q; ++i) comp[k++] = pii(V[i], X[i]);
	sort(comp, comp + k);
	k = unique(comp, comp + k) - comp;
	for (int i = 0; i < n; ++i) {
        A[i] = find(i, A[i]);
        update(A[i], 1);
	}
	for (int i = 0; i < q; ++i) {
        V[i] = find(X[i], V[i]);
	}
	for (int i = 0; i < n; ++i) {
        updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
	}
	vector<int> ret(q);
	for (int it = 0; it < q; ++it) {
        int i = X[it];
        int x = V[it];
        update(A[i], -1);
        updateRange(1, 1, k, A[i], k, 1);
        updatePoint(1, 1, k, A[i], -inf);
        
        A[i] = x;
        update(A[i], 1);
        updateRange(1, 1, k, A[i], k, -1);
        updatePoint(1, 1, k, A[i], i - query(A[i] - 1));
        ret[it] = seg[1];
	}
	return ret;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	16760 KB	Output is correct
2	Correct	19 ms	16760 KB	Output is correct
3	Correct	25 ms	17068 KB	Output is correct
4	Correct	23 ms	17068 KB	Output is correct
5	Correct	19 ms	17252 KB	Output is correct
6	Correct	27 ms	17252 KB	Output is correct
7	Correct	25 ms	17252 KB	Output is correct
8	Correct	19 ms	17252 KB	Output is correct
9	Correct	22 ms	17252 KB	Output is correct
10	Correct	51 ms	17264 KB	Output is correct
11	Correct	23 ms	17264 KB	Output is correct
12	Correct	19 ms	17264 KB	Output is correct
13	Correct	22 ms	17264 KB	Output is correct
14	Correct	18 ms	17264 KB	Output is correct
15	Correct	18 ms	17272 KB	Output is correct
16	Correct	18 ms	17272 KB	Output is correct
17	Correct	22 ms	17272 KB	Output is correct
18	Correct	21 ms	17336 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	16760 KB	Output is correct
2	Correct	19 ms	16760 KB	Output is correct
3	Correct	25 ms	17068 KB	Output is correct
4	Correct	23 ms	17068 KB	Output is correct
5	Correct	19 ms	17252 KB	Output is correct
6	Correct	27 ms	17252 KB	Output is correct
7	Correct	25 ms	17252 KB	Output is correct
8	Correct	19 ms	17252 KB	Output is correct
9	Correct	22 ms	17252 KB	Output is correct
10	Correct	51 ms	17264 KB	Output is correct
11	Correct	23 ms	17264 KB	Output is correct
12	Correct	19 ms	17264 KB	Output is correct
13	Correct	22 ms	17264 KB	Output is correct
14	Correct	18 ms	17264 KB	Output is correct
15	Correct	18 ms	17272 KB	Output is correct
16	Correct	18 ms	17272 KB	Output is correct
17	Correct	22 ms	17272 KB	Output is correct
18	Correct	21 ms	17336 KB	Output is correct
19	Correct	28 ms	17584 KB	Output is correct
20	Correct	35 ms	17720 KB	Output is correct
21	Correct	32 ms	17720 KB	Output is correct
22	Correct	40 ms	17720 KB	Output is correct
23	Correct	45 ms	17720 KB	Output is correct
24	Correct	35 ms	17720 KB	Output is correct
25	Correct	40 ms	17720 KB	Output is correct
26	Correct	30 ms	17720 KB	Output is correct
27	Correct	29 ms	17720 KB	Output is correct
28	Correct	33 ms	17720 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	17720 KB	Output is correct
2	Correct	81 ms	18744 KB	Output is correct
3	Correct	146 ms	19708 KB	Output is correct
4	Correct	140 ms	19768 KB	Output is correct
5	Correct	138 ms	19768 KB	Output is correct
6	Correct	174 ms	19768 KB	Output is correct
7	Correct	135 ms	19768 KB	Output is correct
8	Correct	162 ms	19768 KB	Output is correct
9	Correct	144 ms	19768 KB	Output is correct
10	Correct	113 ms	19768 KB	Output is correct
11	Correct	129 ms	19768 KB	Output is correct
12	Correct	168 ms	19768 KB	Output is correct
13	Correct	115 ms	19768 KB	Output is correct
14	Correct	110 ms	19768 KB	Output is correct
15	Correct	116 ms	19768 KB	Output is correct
16	Correct	115 ms	19768 KB	Output is correct
17	Correct	112 ms	19768 KB	Output is correct
18	Correct	104 ms	19768 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	23 ms	16760 KB	Output is correct
2	Correct	19 ms	16760 KB	Output is correct
3	Correct	25 ms	17068 KB	Output is correct
4	Correct	23 ms	17068 KB	Output is correct
5	Correct	19 ms	17252 KB	Output is correct
6	Correct	27 ms	17252 KB	Output is correct
7	Correct	25 ms	17252 KB	Output is correct
8	Correct	19 ms	17252 KB	Output is correct
9	Correct	22 ms	17252 KB	Output is correct
10	Correct	51 ms	17264 KB	Output is correct
11	Correct	23 ms	17264 KB	Output is correct
12	Correct	19 ms	17264 KB	Output is correct
13	Correct	22 ms	17264 KB	Output is correct
14	Correct	18 ms	17264 KB	Output is correct
15	Correct	18 ms	17272 KB	Output is correct
16	Correct	18 ms	17272 KB	Output is correct
17	Correct	22 ms	17272 KB	Output is correct
18	Correct	21 ms	17336 KB	Output is correct
19	Correct	28 ms	17584 KB	Output is correct
20	Correct	35 ms	17720 KB	Output is correct
21	Correct	32 ms	17720 KB	Output is correct
22	Correct	40 ms	17720 KB	Output is correct
23	Correct	45 ms	17720 KB	Output is correct
24	Correct	35 ms	17720 KB	Output is correct
25	Correct	40 ms	17720 KB	Output is correct
26	Correct	30 ms	17720 KB	Output is correct
27	Correct	29 ms	17720 KB	Output is correct
28	Correct	33 ms	17720 KB	Output is correct
29	Correct	34 ms	17720 KB	Output is correct
30	Correct	81 ms	18744 KB	Output is correct
31	Correct	146 ms	19708 KB	Output is correct
32	Correct	140 ms	19768 KB	Output is correct
33	Correct	138 ms	19768 KB	Output is correct
34	Correct	174 ms	19768 KB	Output is correct
35	Correct	135 ms	19768 KB	Output is correct
36	Correct	162 ms	19768 KB	Output is correct
37	Correct	144 ms	19768 KB	Output is correct
38	Correct	113 ms	19768 KB	Output is correct
39	Correct	129 ms	19768 KB	Output is correct
40	Correct	168 ms	19768 KB	Output is correct
41	Correct	115 ms	19768 KB	Output is correct
42	Correct	110 ms	19768 KB	Output is correct
43	Correct	116 ms	19768 KB	Output is correct
44	Correct	115 ms	19768 KB	Output is correct
45	Correct	112 ms	19768 KB	Output is correct
46	Correct	104 ms	19768 KB	Output is correct
47	Correct	525 ms	24672 KB	Output is correct
48	Correct	2211 ms	40804 KB	Output is correct
49	Correct	2237 ms	42720 KB	Output is correct
50	Correct	2284 ms	42848 KB	Output is correct
51	Correct	2224 ms	42848 KB	Output is correct
52	Correct	2398 ms	42848 KB	Output is correct
53	Correct	2773 ms	42848 KB	Output is correct
54	Correct	2102 ms	42848 KB	Output is correct
55	Correct	2293 ms	42848 KB	Output is correct
56	Correct	2292 ms	42908 KB	Output is correct
57	Correct	2261 ms	42908 KB	Output is correct
58	Correct	2150 ms	42908 KB	Output is correct
59	Correct	1984 ms	42908 KB	Output is correct
60	Correct	1901 ms	42908 KB	Output is correct
61	Correct	1977 ms	42908 KB	Output is correct
62	Correct	1848 ms	42908 KB	Output is correct
63	Correct	1785 ms	42908 KB	Output is correct
64	Correct	1771 ms	42908 KB	Output is correct
65	Correct	1855 ms	42908 KB	Output is correct
66	Correct	1793 ms	42908 KB	Output is correct
67	Correct	1707 ms	42908 KB	Output is correct

답안 #67538

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 40.0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
40.0 / 40.0