oj.uz

답안 #650295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
650295 2022-10-13T12:27:20 Z ymm Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 18 ms 1004 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 N = 500'032;
const int Sa = 4096, Sq = 4096;
int cnt_gt[N];
int val[N];
short cnt_gt_arange[Sa];
short val_arange[Sa];
int mx_qrange[Sq];
int added_to[N];
vector<int> ans;
int n, q, qx[N], qy[N];

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;
}

int mx_init;
void init()
{
	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;
	mx_init = 0;
	Loop (i,0,n) {
		int j =   lower_bound(cmp.begin(), cmp.end(), val[i])
		        - cmp.begin();
		cnt_gt[i] = fen_get(mx-j);
		mx_init = max(mx_init, cnt_gt[i]);
		fen_add(mx-j, 1);
	}
}

#define OPTIM __attribute__((optimize("O3,unroll-loops"),target("avx2")))

OPTIM pair<short,short> do_cnt_gt(int l, int r, short x)
{
	short ans = 0;
	short mx = -32768;
	Loop (i,l,r) {
		ans += val_arange[i] > x;
		mx = cnt_gt_arange[i] > mx? cnt_gt_arange[i]: mx;
	}
	return {ans, mx};
}

OPTIM short do_sub_inrange(int l, int r, short xl, short xr)
{
	short mx = -32768;
	Loop (i,l,r) {
		short cnt = cnt_gt_arange[i];
		short val = val_arange[i];
		cnt -= xl <= val && val < xr;
		mx = cnt > mx? cnt: mx;
		cnt_gt_arange[i] = cnt;
	}
	return mx;
}

OPTIM short do_add_inrange(int l, int r, short xl, short xr)
{
	short mx = -32768;
	Loop (i,l,r) {
		short cnt = cnt_gt_arange[i];
		short val = val_arange[i];
		cnt += xl <= val && val < xr;
		mx = cnt > mx? cnt: mx;
		cnt_gt_arange[i] = cnt;
	}
	return mx;
}



short apply(int al, int ar, int qi, int mx_cnt, const vector<int> &cmp)
{
	int i = qx[qi], x = qy[qi];
	short y =   lower_bound(cmp.begin(), cmp.end(), x)
		  - cmp.begin();
	short mx = -32768;
	if (al < i) {
		int cr = min(ar, i);
		auto [tmp, new_mx] = do_cnt_gt(0, cr-al, y);
		added_to[qi] += tmp;
		mx = max(mx, new_mx);
	}
	if (i+1 < ar) {
		int cl = max(al, i+1);
		if (val[i] < x) {
			short yl = lower_bound(cmp.begin(), cmp.end(),
			                       val[i]) - cmp.begin();
			auto tmp = do_add_inrange(cl-al, ar-al, yl, y);
			mx = max(mx, tmp);
		} else {
			short yr = lower_bound(cmp.begin(), cmp.end(),
			                       val[i]) - cmp.begin();
			auto tmp = do_sub_inrange(cl-al, ar-al, y, yr);
			mx = max(mx, tmp);
		}
	}
	if (al <= i && i < ar) {
		val[i] = x;
		val_arange[i-al] = y;
		cnt_gt[i] = added_to[qi];
		if (cnt_gt[i] - mx_cnt < -16384)
			cnt_gt_arange[i-al] = -16384;
		else
			cnt_gt_arange[i-al] = cnt_gt[i] - mx_cnt;
		mx = max(mx, cnt_gt_arange[i-al]);
	}
	return mx;
}

void solve_arange(int ql, int qr, int al, int ar)
{
	int mx_cnt = ans.size()? ans.back(): mx_init;
	Loop (i,al,ar) {
		if (cnt_gt[i] - mx_cnt < -16384)
			cnt_gt_arange[i-al] = -16384;
		else
			cnt_gt_arange[i-al] = cnt_gt[i] - mx_cnt;
	}
	vector<int> cmp;
	Loop (i,al,ar)
		cmp.push_back(val[i]);
	Loop (i,ql,qr)
		cmp.push_back(qy[i]);
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	Loop (i,al,ar)
		val_arange[i-al] = lower_bound(cmp.begin(), cmp.end(),
		                               val[i]) - cmp.begin();
	Loop (i,ql,qr) {
		int x = apply(al, ar, i, mx_cnt, cmp);
		x += mx_cnt;
		mx_qrange[i-ql] = max(mx_qrange[i-ql], x);
	}
	Loop (i,al,ar) {
		if (cnt_gt[i] - mx_cnt < -16384)
			cnt_gt[i] += (int)cnt_gt_arange[i-al] + 16384;
		else
			cnt_gt[i] = (int)cnt_gt_arange[i-al] + mx_cnt;
	}
}

void solve_qrange(int ql, int qr)
{
	vector<int> ch;
	Loop (i,ql,qr)
		ch.push_back(val[qx[i]]);
	memset(mx_qrange, 0, sizeof(mx_qrange));
	for (int al = 0; al < n; al += Sa) {
		int ar = min(al + Sa, n);
		solve_arange(ql, qr, al, ar);
		Loop (i,ql,qr)
			val[qx[i]] = ch[i-ql];
	}
	Loop (i,ql,qr)
		val[qx[i]] = qy[i];
	Loop (i,ql,qr)
		ans.push_back(mx_qrange[i-ql]);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	n = A.size();
	Loop (i,0,n)
		val[i] = A[i];
	q = X.size();
	Loop (i,0,q) {
		qx[i] = X[i];
		qy[i] = V[i];
	}
	init();
	for (int ql = 0; ql < q; ql += Sq) {
		int qr = min(ql+Sq, q);
		solve_qrange(ql, qr);
	}
	return ans;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 484 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 3 ms 580 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 5 ms 468 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 484 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 3 ms 580 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Incorrect 16 ms 960 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 1004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 500 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 484 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 3 ms 580 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 5 ms 468 KB Output is correct
19 Incorrect 16 ms 960 KB Output isn't correct
20 Halted 0 ms 0 KB -