답안 #369847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369847	2021-02-22T15:53:50 Z	pure_mem	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3392 ms	41436 KB

bubblesort2

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

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e6 + 12;

int n, q, m, t[N * 4], tt[N * 4];
vector< pair<int, int> > ord;

void push(int v){
	if(!tt[v])
		return;
	t[v * 2] += tt[v], t[v * 2 + 1] += tt[v];
	tt[v * 2] += tt[v], tt[v * 2 + 1] += tt[v];
	tt[v] = 0;
}

void upd(int v, int tl, int tr, int l, int r, int val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		t[v] += val, tt[v] += val;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val);
	upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get_pos(pair<int, int> x){
	return lower_bound(ord.begin(), ord.end(), x) - ord.begin() + 1;
}

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++)
		ord.push_back(MP(A[i], i));
	for(int i = 0;i < q;i++)
		ord.push_back(MP(V[i], X[i]));
	sort(ord.begin(), ord.end());
	ord.erase(unique(ord.begin(), ord.end()), ord.end());
	m = (int)ord.size();
	for(int i = 0;i < n;i++){
		int pos1 = get_pos(MP(A[i], i));
		upd(1, 1, m, pos1, pos1, i + 1);
		int pos2 = get_pos(MP(A[i], -1));
		upd(1, 1, m, pos2, m, -1);		
	}
	vector<int> answer(q);
	for(int i = 0;i < q;i++){
		int pos1 = get_pos(MP(A[X[i]], X[i]));
		upd(1, 1, m, pos1, pos1, -X[i] - 1);
		int pos2 = get_pos(MP(A[X[i]], -1));
		upd(1, 1, m, pos2, m, 1);
		A[X[i]] = V[i];		
		pos1 = get_pos(MP(A[X[i]], X[i]));
		upd(1, 1, m, pos1, pos1, X[i] + 1);
		pos2 = get_pos(MP(A[X[i]], -1));
		upd(1, 1, m, pos2, m, -1);
		answer[i] = t[1];
	}
	return answer;
}

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	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	6 ms	620 KB	Output is correct
5	Correct	6 ms	620 KB	Output is correct
6	Correct	6 ms	620 KB	Output is correct
7	Correct	6 ms	492 KB	Output is correct
8	Correct	6 ms	620 KB	Output is correct
9	Correct	6 ms	620 KB	Output is correct
10	Correct	5 ms	620 KB	Output is correct
11	Correct	6 ms	620 KB	Output is correct
12	Correct	5 ms	620 KB	Output is correct
13	Correct	5 ms	620 KB	Output is correct
14	Correct	5 ms	620 KB	Output is correct
15	Correct	5 ms	620 KB	Output is correct
16	Correct	5 ms	620 KB	Output is correct
17	Correct	5 ms	620 KB	Output is correct
18	Correct	5 ms	620 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	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	6 ms	620 KB	Output is correct
5	Correct	6 ms	620 KB	Output is correct
6	Correct	6 ms	620 KB	Output is correct
7	Correct	6 ms	492 KB	Output is correct
8	Correct	6 ms	620 KB	Output is correct
9	Correct	6 ms	620 KB	Output is correct
10	Correct	5 ms	620 KB	Output is correct
11	Correct	6 ms	620 KB	Output is correct
12	Correct	5 ms	620 KB	Output is correct
13	Correct	5 ms	620 KB	Output is correct
14	Correct	5 ms	620 KB	Output is correct
15	Correct	5 ms	620 KB	Output is correct
16	Correct	5 ms	620 KB	Output is correct
17	Correct	5 ms	620 KB	Output is correct
18	Correct	5 ms	620 KB	Output is correct
19	Correct	22 ms	1260 KB	Output is correct
20	Correct	24 ms	1260 KB	Output is correct
21	Correct	24 ms	1260 KB	Output is correct
22	Correct	30 ms	1260 KB	Output is correct
23	Correct	23 ms	1260 KB	Output is correct
24	Correct	23 ms	1260 KB	Output is correct
25	Correct	27 ms	1260 KB	Output is correct
26	Correct	26 ms	1388 KB	Output is correct
27	Correct	22 ms	1260 KB	Output is correct
28	Correct	22 ms	1260 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	1512 KB	Output is correct
2	Correct	106 ms	3044 KB	Output is correct
3	Correct	199 ms	5216 KB	Output is correct
4	Correct	215 ms	5088 KB	Output is correct
5	Correct	195 ms	5216 KB	Output is correct
6	Correct	201 ms	5216 KB	Output is correct
7	Correct	198 ms	5088 KB	Output is correct
8	Correct	187 ms	5088 KB	Output is correct
9	Correct	190 ms	5088 KB	Output is correct
10	Correct	147 ms	4192 KB	Output is correct
11	Correct	147 ms	4320 KB	Output is correct
12	Correct	142 ms	4324 KB	Output is correct
13	Correct	145 ms	4192 KB	Output is correct
14	Correct	157 ms	4192 KB	Output is correct
15	Correct	144 ms	4192 KB	Output is correct
16	Correct	135 ms	4192 KB	Output is correct
17	Correct	143 ms	4192 KB	Output is correct
18	Correct	139 ms	4192 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	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	6 ms	620 KB	Output is correct
5	Correct	6 ms	620 KB	Output is correct
6	Correct	6 ms	620 KB	Output is correct
7	Correct	6 ms	492 KB	Output is correct
8	Correct	6 ms	620 KB	Output is correct
9	Correct	6 ms	620 KB	Output is correct
10	Correct	5 ms	620 KB	Output is correct
11	Correct	6 ms	620 KB	Output is correct
12	Correct	5 ms	620 KB	Output is correct
13	Correct	5 ms	620 KB	Output is correct
14	Correct	5 ms	620 KB	Output is correct
15	Correct	5 ms	620 KB	Output is correct
16	Correct	5 ms	620 KB	Output is correct
17	Correct	5 ms	620 KB	Output is correct
18	Correct	5 ms	620 KB	Output is correct
19	Correct	22 ms	1260 KB	Output is correct
20	Correct	24 ms	1260 KB	Output is correct
21	Correct	24 ms	1260 KB	Output is correct
22	Correct	30 ms	1260 KB	Output is correct
23	Correct	23 ms	1260 KB	Output is correct
24	Correct	23 ms	1260 KB	Output is correct
25	Correct	27 ms	1260 KB	Output is correct
26	Correct	26 ms	1388 KB	Output is correct
27	Correct	22 ms	1260 KB	Output is correct
28	Correct	22 ms	1260 KB	Output is correct
29	Correct	34 ms	1512 KB	Output is correct
30	Correct	106 ms	3044 KB	Output is correct
31	Correct	199 ms	5216 KB	Output is correct
32	Correct	215 ms	5088 KB	Output is correct
33	Correct	195 ms	5216 KB	Output is correct
34	Correct	201 ms	5216 KB	Output is correct
35	Correct	198 ms	5088 KB	Output is correct
36	Correct	187 ms	5088 KB	Output is correct
37	Correct	190 ms	5088 KB	Output is correct
38	Correct	147 ms	4192 KB	Output is correct
39	Correct	147 ms	4320 KB	Output is correct
40	Correct	142 ms	4324 KB	Output is correct
41	Correct	145 ms	4192 KB	Output is correct
42	Correct	157 ms	4192 KB	Output is correct
43	Correct	144 ms	4192 KB	Output is correct
44	Correct	135 ms	4192 KB	Output is correct
45	Correct	143 ms	4192 KB	Output is correct
46	Correct	139 ms	4192 KB	Output is correct
47	Correct	742 ms	18616 KB	Output is correct
48	Correct	3055 ms	39452 KB	Output is correct
49	Correct	3392 ms	41192 KB	Output is correct
50	Correct	3333 ms	41036 KB	Output is correct
51	Correct	3283 ms	41176 KB	Output is correct
52	Correct	3253 ms	41032 KB	Output is correct
53	Correct	3249 ms	41108 KB	Output is correct
54	Correct	2935 ms	41032 KB	Output is correct
55	Correct	3112 ms	41052 KB	Output is correct
56	Correct	2892 ms	41100 KB	Output is correct
57	Correct	3174 ms	41032 KB	Output is correct
58	Correct	2875 ms	41032 KB	Output is correct
59	Correct	2705 ms	41176 KB	Output is correct
60	Correct	2690 ms	41164 KB	Output is correct
61	Correct	2628 ms	41152 KB	Output is correct
62	Correct	2444 ms	41044 KB	Output is correct
63	Correct	2481 ms	41436 KB	Output is correct
64	Correct	2446 ms	41288 KB	Output is correct
65	Correct	2271 ms	41132 KB	Output is correct
66	Correct	2305 ms	41128 KB	Output is correct
67	Correct	2281 ms	41160 KB	Output is correct

답안 #369847

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