oj.uz

답안 #650435

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650435 2022-10-13T18:19:45 Z ymm Bubble Sort 2 (JOI18_bubblesort2) C++17
60 / 100
 9000 ms 29572 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")

const int S = 2048+512+256;
const int N = 500'032 + S;
int seg_mx[S*2];
int seg_cnt[S*2];
int qans[N], added_to[N];
int val[N], cnt[N], val_srt[N], srt_ind[N];
int n;

void add_seg(int l, int r, int x)
{
	#define MAX(x, y) ((x)>(y)?(x):(y))
	#define UP(i) seg_mx[i] =   MAX(seg_mx[2*(i)],\
	                                seg_mx[2*(i)+1])\
	                          + seg_cnt[i];
	l += S; r += S;
	for (;;) {
		if (l != r && (l&1)) {
			seg_mx[l] += x;
			seg_cnt[l] += x;
			++l;
		}
		if (l != r && (r&1)) {
			--r;
			seg_mx[r] += x;
			seg_cnt[r] += x;
		}
		l /= 2; r /= 2;
		if (l == 0) break;
		if (l > 1) UP(l-1);
		if (r < S) UP(r);
	}
}

void build_seg(int l)
{
	Loop (i,S,2*S) {
		seg_cnt[i] = cnt[srt_ind[l + i-S]];
		seg_mx[i] = seg_cnt[i];
	}
	LoopR (i,1,S) {
		seg_mx[i] = max(seg_mx[2*i], seg_mx[2*i+1]);
		seg_cnt[i] = 0;
	}
}

void flush_seg(int l)
{
	Loop (i,1,S) {
		seg_cnt[2*i] += seg_cnt[i];
		seg_cnt[2*i+1] += seg_cnt[i];
	}
	Loop (i,S,2*S)
		cnt[srt_ind[l + i-S]] = seg_cnt[i];
}

int get_gt(int l, int x)
{
	return S - (  upper_bound(val_srt + l, val_srt + l + S, x)
	            - (val_srt + l));
}

void up_range(int l, int xl, int xr, int val)
{
	xl = lower_bound(val_srt + l, val_srt + l + S, xl) - val_srt - l;
	xr = lower_bound(val_srt + l, val_srt + l + S, xr) - val_srt - l;
	if (xl < xr)
		add_seg(xl, xr, val);
}

void mov(int i, int x)
{
	int j = i - i%S;
	for (; srt_ind[j] != i; ++j);
	int dst =   lower_bound(val_srt + i-i%S, val_srt + i-i%S + S, x)
	          - val_srt;
	if (j < dst) {
		--dst;
		Loop (k, j, dst) {
			val_srt[k] = val_srt[k+1];
			srt_ind[k] = srt_ind[k+1];
		}
	} else {
		LoopR (k, dst, j) {
			val_srt[k+1] = val_srt[k];
			srt_ind[k+1] = srt_ind[k];
		}
	}
	val_srt[dst] = x;
	srt_ind[dst] = i;
}

void up(int l, int qi, int i, int pre, int x)
{
	if (i < l) {
		int val = pre < x? 1: -1;
		int xl = pre < x? pre: x;
		int xr = pre < x? x: pre;
		up_range(l, xl, xr, val);
	} else if (l <= i && i < l + S) {
		int cnt_gt = added_to[qi];
		flush_seg(i - i%S);
		for (int j = i - i%S; j < i; ++j)
			cnt_gt += val[j] > x;
		cnt[i] = cnt_gt;
		val[i] = x;
		for (int j = i + 1; j < i - i%S + S; ++j)
			cnt[j] += (x > val[j]) - (pre > val[j]);
		mov(i, x);
		build_seg(i - i%S);
	} else {
		added_to[qi] += get_gt(l, x);
	}
}

namespace init {
int fen[N];
void fen_add(int i, int x)
{
	++i;
	while (i < N) {
		fen[i] += x;
		i += i & -i;
	}
}
int fen_get(int r)
{
	int ans = 0;
	while (r > 0) {
		ans += fen[r];
		r -= r & -r;
	}
	return ans;
}
 
void init(vector<int> A)
{
	static pii pii_srt[N];
	n = A.size();
	Loop (i,0,n) {
		val[i] = A[i];
		pii_srt[i] = {val[i], i};
	}
	Loop (i,n,N) {
		val[i] = 1e9+10;
		pii_srt[i] = {val[i], i};
	}
	for (int l = 0; l < n; l += S) {
		sort(pii_srt+l, pii_srt+l+S);
		Loop (i,l,l+S) {
			val_srt[i] = pii_srt[i].first;
			srt_ind[i] = pii_srt[i].second;
		}
	}
	vector<int> cmp(val, val+N);
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	int mx = cmp.size() - 1;
	Loop (i,0,n) {
		int j =   lower_bound(cmp.begin(), cmp.end(), val[i])
		        - cmp.begin();
		cnt[i] = fen_get(mx-j);
		fen_add(mx-j, 1);
	}
}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	init::init(A);
	vector<int> ans;
	vector<int> U(X.size());
	Loop (i,0,X.size()) {
		U[i] = val[X[i]];
		val[X[i]] = V[i];
	}
	LoopR (i,0,X.size())
		val[X[i]] = U[i];
	for (int l = 0; l < n; l += S) {
		build_seg(l);
		Loop (i,0,X.size()) {
			up(l, i, X[i], U[i], V[i]);
			qans[i] = max(qans[i], seg_mx[1]);
		}
	}
	Loop (i,0,X.size())
		ans.push_back(qans[i]);
	return ans;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8276 KB Output is correct
2 Correct 26 ms 8240 KB Output is correct
3 Correct 44 ms 8276 KB Output is correct
4 Correct 41 ms 8296 KB Output is correct
5 Correct 44 ms 8276 KB Output is correct
6 Correct 43 ms 8276 KB Output is correct
7 Correct 42 ms 8288 KB Output is correct
8 Correct 43 ms 8276 KB Output is correct
9 Correct 44 ms 8296 KB Output is correct
10 Correct 44 ms 8424 KB Output is correct
11 Correct 40 ms 8276 KB Output is correct
12 Correct 44 ms 8276 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 43 ms 8276 KB Output is correct
15 Correct 42 ms 8320 KB Output is correct
16 Correct 41 ms 8276 KB Output is correct
17 Correct 43 ms 8276 KB Output is correct
18 Correct 43 ms 8276 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8276 KB Output is correct
2 Correct 26 ms 8240 KB Output is correct
3 Correct 44 ms 8276 KB Output is correct
4 Correct 41 ms 8296 KB Output is correct
5 Correct 44 ms 8276 KB Output is correct
6 Correct 43 ms 8276 KB Output is correct
7 Correct 42 ms 8288 KB Output is correct
8 Correct 43 ms 8276 KB Output is correct
9 Correct 44 ms 8296 KB Output is correct
10 Correct 44 ms 8424 KB Output is correct
11 Correct 40 ms 8276 KB Output is correct
12 Correct 44 ms 8276 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 43 ms 8276 KB Output is correct
15 Correct 42 ms 8320 KB Output is correct
16 Correct 41 ms 8276 KB Output is correct
17 Correct 43 ms 8276 KB Output is correct
18 Correct 43 ms 8276 KB Output is correct
19 Correct 122 ms 8472 KB Output is correct
20 Correct 142 ms 8532 KB Output is correct
21 Correct 139 ms 8532 KB Output is correct
22 Correct 137 ms 8532 KB Output is correct
23 Correct 142 ms 8532 KB Output is correct
24 Correct 140 ms 8500 KB Output is correct
25 Correct 137 ms 8504 KB Output is correct
26 Correct 135 ms 8532 KB Output is correct
27 Correct 137 ms 8472 KB Output is correct
28 Correct 135 ms 8532 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 8924 KB Output is correct
2 Correct 453 ms 9528 KB Output is correct
3 Correct 935 ms 10188 KB Output is correct
4 Correct 934 ms 10188 KB Output is correct
5 Correct 899 ms 10196 KB Output is correct
6 Correct 903 ms 10188 KB Output is correct
7 Correct 879 ms 10184 KB Output is correct
8 Correct 886 ms 10192 KB Output is correct
9 Correct 858 ms 10116 KB Output is correct
10 Correct 777 ms 10188 KB Output is correct
11 Correct 779 ms 10116 KB Output is correct
12 Correct 788 ms 10112 KB Output is correct
13 Correct 764 ms 10196 KB Output is correct
14 Correct 751 ms 10196 KB Output is correct
15 Correct 772 ms 10188 KB Output is correct
16 Correct 746 ms 10188 KB Output is correct
17 Correct 756 ms 10188 KB Output is correct
18 Correct 757 ms 10196 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 8276 KB Output is correct
2 Correct 26 ms 8240 KB Output is correct
3 Correct 44 ms 8276 KB Output is correct
4 Correct 41 ms 8296 KB Output is correct
5 Correct 44 ms 8276 KB Output is correct
6 Correct 43 ms 8276 KB Output is correct
7 Correct 42 ms 8288 KB Output is correct
8 Correct 43 ms 8276 KB Output is correct
9 Correct 44 ms 8296 KB Output is correct
10 Correct 44 ms 8424 KB Output is correct
11 Correct 40 ms 8276 KB Output is correct
12 Correct 44 ms 8276 KB Output is correct
13 Correct 42 ms 8300 KB Output is correct
14 Correct 43 ms 8276 KB Output is correct
15 Correct 42 ms 8320 KB Output is correct
16 Correct 41 ms 8276 KB Output is correct
17 Correct 43 ms 8276 KB Output is correct
18 Correct 43 ms 8276 KB Output is correct
19 Correct 122 ms 8472 KB Output is correct
20 Correct 142 ms 8532 KB Output is correct
21 Correct 139 ms 8532 KB Output is correct
22 Correct 137 ms 8532 KB Output is correct
23 Correct 142 ms 8532 KB Output is correct
24 Correct 140 ms 8500 KB Output is correct
25 Correct 137 ms 8504 KB Output is correct
26 Correct 135 ms 8532 KB Output is correct
27 Correct 137 ms 8472 KB Output is correct
28 Correct 135 ms 8532 KB Output is correct
29 Correct 52 ms 8924 KB Output is correct
30 Correct 453 ms 9528 KB Output is correct
31 Correct 935 ms 10188 KB Output is correct
32 Correct 934 ms 10188 KB Output is correct
33 Correct 899 ms 10196 KB Output is correct
34 Correct 903 ms 10188 KB Output is correct
35 Correct 879 ms 10184 KB Output is correct
36 Correct 886 ms 10192 KB Output is correct
37 Correct 858 ms 10116 KB Output is correct
38 Correct 777 ms 10188 KB Output is correct
39 Correct 779 ms 10116 KB Output is correct
40 Correct 788 ms 10112 KB Output is correct
41 Correct 764 ms 10196 KB Output is correct
42 Correct 751 ms 10196 KB Output is correct
43 Correct 772 ms 10188 KB Output is correct
44 Correct 746 ms 10188 KB Output is correct
45 Correct 756 ms 10188 KB Output is correct
46 Correct 757 ms 10196 KB Output is correct
47 Correct 3503 ms 15388 KB Output is correct
48 Execution timed out 9071 ms 29572 KB Time limit exceeded
49 Halted 0 ms 0 KB -