oj.uz

답안 #650381

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650381 2022-10-13T16:02:06 Z ymm Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 10060 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;

const int S = 1;
const int N = 500'032 + S;
int seg_mx[N/S][S*2];
int seg_cnt[N/S][S*2];
int val[N], cnt[N], val_srt[N], srt_ind[N];
int n;

void add_seg(int l, int r, int x, int t)
{
	#define UP(i) seg_mx[t][i] =   max(seg_mx[t][2*(i)],\
	                                   seg_mx[t][2*(i)+1])\
	                             + seg_cnt[t][i];
	l += S; r += S;
	for (;;) {
		if (l&1) {
			seg_mx[t][l] += x;
			seg_cnt[t][l] += x;
			++l;
		}
		if (l == r) break;
		if (r&1) {
			--r;
			seg_mx[t][r] += x;
			seg_cnt[t][r] += x;
		}
		if (l == r) break;
		l /= 2; r /= 2;
	}
	LoopR (i,1,S)
		UP(i);
}

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

void flush_seg(int t)
{
	Loop (i,1,S) {
		seg_cnt[t][2*i] += seg_cnt[t][i];
		seg_cnt[t][2*i+1] += seg_cnt[t][i];
	}
	Loop (i,S,2*S)
		cnt[srt_ind[t*S + i-S]] = seg_cnt[t][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, l/S);
}

void mov(int i, int x)
{
	int j = i - i%S;
	for (; srt_ind[j] != i; ++j);
	val_srt[j] = x;
	while ((j+1)%S && val_srt[j] > val_srt[j+1]) {
		swap(val_srt[j], val_srt[j+1]);
		swap(srt_ind[j], srt_ind[j+1]);
		++j;
	}
	while (j%S && val_srt[j] < val_srt[j-1]) {
		swap(val_srt[j], val_srt[j-1]);
		swap(srt_ind[j], srt_ind[j-1]);
		--j;
	}
}

void up(int i, int x)
{
	int pre = val[i];
	int cnt_gt = 0;
	for (int l = 0; l < i - i%S; l += S)
		cnt_gt += get_gt(l, x);
	flush_seg(i/S);
	val[i] = x;
	for (int j = i - i%S; j < i; ++j)
		cnt_gt += val[j] > x;
	cnt[i] = cnt_gt;
	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/S);
	int val = pre < x? 1: -1;
	int xl = pre < x? pre: x;
	int xr = pre < x? x: pre;
	for (int l = i - i%S + S; l < n; l += S)
		up_range(l, xl, xr, val);
}

int get()
{
	int mx = 0;
	for (int l = 0; l < n; l += S)
		mx = max(seg_mx[l/S][1], mx);
	return mx;
}

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);
	}
	for (int l = 0; l < n; l += S)
		build_seg(l/S);
}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	init::init(A);
	vector<int> ans;
	Loop (i,0,X.size()) {
		up(X[i], V[i]);
		ans.push_back(get());
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 20 ms 8200 KB Output is correct
3 Correct 59 ms 8276 KB Output is correct
4 Correct 56 ms 8276 KB Output is correct
5 Correct 50 ms 8268 KB Output is correct
6 Correct 39 ms 8276 KB Output is correct
7 Correct 43 ms 8276 KB Output is correct
8 Correct 47 ms 8304 KB Output is correct
9 Correct 49 ms 8236 KB Output is correct
10 Correct 44 ms 8276 KB Output is correct
11 Correct 46 ms 8276 KB Output is correct
12 Correct 52 ms 8280 KB Output is correct
13 Correct 42 ms 8272 KB Output is correct
14 Correct 41 ms 8228 KB Output is correct
15 Correct 40 ms 8276 KB Output is correct
16 Correct 39 ms 8236 KB Output is correct
17 Correct 45 ms 8240 KB Output is correct
18 Correct 40 ms 8244 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 20 ms 8200 KB Output is correct
3 Correct 59 ms 8276 KB Output is correct
4 Correct 56 ms 8276 KB Output is correct
5 Correct 50 ms 8268 KB Output is correct
6 Correct 39 ms 8276 KB Output is correct
7 Correct 43 ms 8276 KB Output is correct
8 Correct 47 ms 8304 KB Output is correct
9 Correct 49 ms 8236 KB Output is correct
10 Correct 44 ms 8276 KB Output is correct
11 Correct 46 ms 8276 KB Output is correct
12 Correct 52 ms 8280 KB Output is correct
13 Correct 42 ms 8272 KB Output is correct
14 Correct 41 ms 8228 KB Output is correct
15 Correct 40 ms 8276 KB Output is correct
16 Correct 39 ms 8236 KB Output is correct
17 Correct 45 ms 8240 KB Output is correct
18 Correct 40 ms 8244 KB Output is correct
19 Correct 545 ms 8544 KB Output is correct
20 Correct 761 ms 8660 KB Output is correct
21 Correct 599 ms 8580 KB Output is correct
22 Correct 695 ms 8660 KB Output is correct
23 Correct 514 ms 8660 KB Output is correct
24 Correct 516 ms 8660 KB Output is correct
25 Correct 473 ms 8660 KB Output is correct
26 Correct 488 ms 8660 KB Output is correct
27 Correct 434 ms 8660 KB Output is correct
28 Correct 442 ms 8584 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 628 ms 9300 KB Output is correct
2 Execution timed out 9073 ms 10060 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 8148 KB Output is correct
2 Correct 20 ms 8200 KB Output is correct
3 Correct 59 ms 8276 KB Output is correct
4 Correct 56 ms 8276 KB Output is correct
5 Correct 50 ms 8268 KB Output is correct
6 Correct 39 ms 8276 KB Output is correct
7 Correct 43 ms 8276 KB Output is correct
8 Correct 47 ms 8304 KB Output is correct
9 Correct 49 ms 8236 KB Output is correct
10 Correct 44 ms 8276 KB Output is correct
11 Correct 46 ms 8276 KB Output is correct
12 Correct 52 ms 8280 KB Output is correct
13 Correct 42 ms 8272 KB Output is correct
14 Correct 41 ms 8228 KB Output is correct
15 Correct 40 ms 8276 KB Output is correct
16 Correct 39 ms 8236 KB Output is correct
17 Correct 45 ms 8240 KB Output is correct
18 Correct 40 ms 8244 KB Output is correct
19 Correct 545 ms 8544 KB Output is correct
20 Correct 761 ms 8660 KB Output is correct
21 Correct 599 ms 8580 KB Output is correct
22 Correct 695 ms 8660 KB Output is correct
23 Correct 514 ms 8660 KB Output is correct
24 Correct 516 ms 8660 KB Output is correct
25 Correct 473 ms 8660 KB Output is correct
26 Correct 488 ms 8660 KB Output is correct
27 Correct 434 ms 8660 KB Output is correct
28 Correct 442 ms 8584 KB Output is correct
29 Correct 628 ms 9300 KB Output is correct
30 Execution timed out 9073 ms 10060 KB Time limit exceeded
31 Halted 0 ms 0 KB -