oj.uz

답안 #160482

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160482 2019-10-27T16:01:58 Z iefnah06 Bubble Sort 2 (JOI18_bubblesort2) C++11
100 / 100
 3129 ms 99064 KB 
#include "bubblesort2.h"

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int INF = 1e9;

const int MAXN = 5.1e5;
const int MAXQ = 5.1e5;
const int MAXS = MAXN + MAXQ;
int N, Q;

struct seg {
	seg* ch[2];
	ll maxval;
	ll lazyval;

	seg() {
		maxval = lazyval = 0;
	}

	void increment(ll a) {
		maxval += a;
		lazyval += a;
	}

	void update() {
		assert(ch[0] && ch[1]);
		maxval = lazyval + max(ch[0]->maxval, ch[1]->maxval);
	}
};
seg nodes[MAXS*2];
int NODE = 0;
seg* ROOT;

pair<int, int> pairs[MAXS];
int S;

seg* build(int x = 0, int y = S) {
	seg* n = &nodes[NODE++];
	if (y - x > 1) {
		int z = (x + y) / 2;
		n->ch[0] = build(x, z);
		n->ch[1] = build(z, y);
		n->update();
	}
	return n;
}

void update(int l, int r, int v, int x, int y, seg* n) {
	if (l <= x && y <= r) {
		n->increment(v);
	} else {
		int z = (x + y) / 2;
		if (l < z) {
			update(l, r, v, x, z, n->ch[0]);
		}
		if (z < r) {
			update(l, r, v, z, y, n->ch[1]);
		}
		n->update();
	}
}

ll slow[MAXN];

void update(int l, int r, int v) {
	if (l < r) {
		update(l, r, v, 0, S, ROOT);
	}
}

ll query() {
	return ROOT->maxval;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	N = int(A.size());
	Q = int(X.size());

	S = 0;
	for (int i = 0; i < N; i++) {
		pairs[S++] = {A[i], i};
	}
	for (int i = 0; i < Q; i++) {
		pairs[S++] = {V[i], X[i]};
	}
	sort(pairs, pairs + S);
	S = int(unique(pairs, pairs + S) - pairs);

	auto modify = [&](int v, int i, int k) -> void {
		int j = int(lower_bound(pairs, pairs + S, pair<int, int>(v, i)) - pairs);
		assert(make_pair(v, i) == pairs[j]);
		update(j, j+1, k * (INF + i));
		update(j+1, S, k * -1);
	};

	ROOT = build();
	update(0, S, -INF);
	for (int i = 0; i < N; i++) {
		modify(A[i], i, 1);
	}
	
	vector<int> answer(Q);
	for (int q = 0; q < Q; q++) {
		modify(A[X[q]], X[q], -1);
		modify(V[q], X[q], 1);
		A[X[q]] = V[q];
		answer[q] = query();
	}
	return answer;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 64252 KB Output is correct
2 Correct 53 ms 64388 KB Output is correct
3 Correct 56 ms 64248 KB Output is correct
4 Correct 56 ms 64248 KB Output is correct
5 Correct 54 ms 64376 KB Output is correct
6 Correct 55 ms 64248 KB Output is correct
7 Correct 55 ms 64248 KB Output is correct
8 Correct 57 ms 64376 KB Output is correct
9 Correct 57 ms 64220 KB Output is correct
10 Correct 54 ms 64368 KB Output is correct
11 Correct 55 ms 64228 KB Output is correct
12 Correct 61 ms 64248 KB Output is correct
13 Correct 55 ms 64376 KB Output is correct
14 Correct 56 ms 64248 KB Output is correct
15 Correct 56 ms 64248 KB Output is correct
16 Correct 58 ms 64376 KB Output is correct
17 Correct 54 ms 64248 KB Output is correct
18 Correct 54 ms 64248 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 64252 KB Output is correct
2 Correct 53 ms 64388 KB Output is correct
3 Correct 56 ms 64248 KB Output is correct
4 Correct 56 ms 64248 KB Output is correct
5 Correct 54 ms 64376 KB Output is correct
6 Correct 55 ms 64248 KB Output is correct
7 Correct 55 ms 64248 KB Output is correct
8 Correct 57 ms 64376 KB Output is correct
9 Correct 57 ms 64220 KB Output is correct
10 Correct 54 ms 64368 KB Output is correct
11 Correct 55 ms 64228 KB Output is correct
12 Correct 61 ms 64248 KB Output is correct
13 Correct 55 ms 64376 KB Output is correct
14 Correct 56 ms 64248 KB Output is correct
15 Correct 56 ms 64248 KB Output is correct
16 Correct 58 ms 64376 KB Output is correct
17 Correct 54 ms 64248 KB Output is correct
18 Correct 54 ms 64248 KB Output is correct
19 Correct 67 ms 64544 KB Output is correct
20 Correct 71 ms 64768 KB Output is correct
21 Correct 72 ms 64760 KB Output is correct
22 Correct 70 ms 64760 KB Output is correct
23 Correct 69 ms 64748 KB Output is correct
24 Correct 69 ms 64760 KB Output is correct
25 Correct 68 ms 64760 KB Output is correct
26 Correct 70 ms 64760 KB Output is correct
27 Correct 70 ms 64744 KB Output is correct
28 Correct 74 ms 64760 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 64760 KB Output is correct
2 Correct 137 ms 65584 KB Output is correct
3 Correct 218 ms 66936 KB Output is correct
4 Correct 213 ms 67064 KB Output is correct
5 Correct 217 ms 66924 KB Output is correct
6 Correct 225 ms 67016 KB Output is correct
7 Correct 210 ms 67000 KB Output is correct
8 Correct 208 ms 67064 KB Output is correct
9 Correct 213 ms 66912 KB Output is correct
10 Correct 165 ms 67192 KB Output is correct
11 Correct 163 ms 67112 KB Output is correct
12 Correct 162 ms 67192 KB Output is correct
13 Correct 165 ms 66936 KB Output is correct
14 Correct 160 ms 66992 KB Output is correct
15 Correct 159 ms 66996 KB Output is correct
16 Correct 152 ms 67064 KB Output is correct
17 Correct 150 ms 67148 KB Output is correct
18 Correct 153 ms 67064 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 64252 KB Output is correct
2 Correct 53 ms 64388 KB Output is correct
3 Correct 56 ms 64248 KB Output is correct
4 Correct 56 ms 64248 KB Output is correct
5 Correct 54 ms 64376 KB Output is correct
6 Correct 55 ms 64248 KB Output is correct
7 Correct 55 ms 64248 KB Output is correct
8 Correct 57 ms 64376 KB Output is correct
9 Correct 57 ms 64220 KB Output is correct
10 Correct 54 ms 64368 KB Output is correct
11 Correct 55 ms 64228 KB Output is correct
12 Correct 61 ms 64248 KB Output is correct
13 Correct 55 ms 64376 KB Output is correct
14 Correct 56 ms 64248 KB Output is correct
15 Correct 56 ms 64248 KB Output is correct
16 Correct 58 ms 64376 KB Output is correct
17 Correct 54 ms 64248 KB Output is correct
18 Correct 54 ms 64248 KB Output is correct
19 Correct 67 ms 64544 KB Output is correct
20 Correct 71 ms 64768 KB Output is correct
21 Correct 72 ms 64760 KB Output is correct
22 Correct 70 ms 64760 KB Output is correct
23 Correct 69 ms 64748 KB Output is correct
24 Correct 69 ms 64760 KB Output is correct
25 Correct 68 ms 64760 KB Output is correct
26 Correct 70 ms 64760 KB Output is correct
27 Correct 70 ms 64744 KB Output is correct
28 Correct 74 ms 64760 KB Output is correct
29 Correct 74 ms 64760 KB Output is correct
30 Correct 137 ms 65584 KB Output is correct
31 Correct 218 ms 66936 KB Output is correct
32 Correct 213 ms 67064 KB Output is correct
33 Correct 217 ms 66924 KB Output is correct
34 Correct 225 ms 67016 KB Output is correct
35 Correct 210 ms 67000 KB Output is correct
36 Correct 208 ms 67064 KB Output is correct
37 Correct 213 ms 66912 KB Output is correct
38 Correct 165 ms 67192 KB Output is correct
39 Correct 163 ms 67112 KB Output is correct
40 Correct 162 ms 67192 KB Output is correct
41 Correct 165 ms 66936 KB Output is correct
42 Correct 160 ms 66992 KB Output is correct
43 Correct 159 ms 66996 KB Output is correct
44 Correct 152 ms 67064 KB Output is correct
45 Correct 150 ms 67148 KB Output is correct
46 Correct 153 ms 67064 KB Output is correct
47 Correct 848 ms 74308 KB Output is correct
48 Correct 2810 ms 95976 KB Output is correct
49 Correct 3129 ms 98620 KB Output is correct
50 Correct 2945 ms 98752 KB Output is correct
51 Correct 3039 ms 98552 KB Output is correct
52 Correct 2968 ms 98680 KB Output is correct
53 Correct 2971 ms 98748 KB Output is correct
54 Correct 2718 ms 98800 KB Output is correct
55 Correct 2858 ms 99064 KB Output is correct
56 Correct 2652 ms 98936 KB Output is correct
57 Correct 2779 ms 98904 KB Output is correct
58 Correct 2631 ms 98928 KB Output is correct
59 Correct 2382 ms 97480 KB Output is correct
60 Correct 2305 ms 97604 KB Output is correct
61 Correct 2302 ms 97500 KB Output is correct
62 Correct 2199 ms 97452 KB Output is correct
63 Correct 2283 ms 97528 KB Output is correct
64 Correct 2276 ms 97400 KB Output is correct
65 Correct 2067 ms 97288 KB Output is correct
66 Correct 2040 ms 97272 KB Output is correct
67 Correct 2036 ms 97144 KB Output is correct