Submission #633936

#	Time	Username	Problem	Language	Result	Execution time	Memory
633936		Arinoor	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3216 ms	66832 KiB

bubblesort2

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

#define all(x)			x.begin(), x.end()
#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define bug(x)			cerr << #x << " : " << x << '\n'
#define mid				((l + r) >> 1)
#define lc				(id << 1)
#define rc				(lc | 1)

typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int inf = 1e9 + 10;

int n, q, m, a[maxn];
int seg[maxn << 2], lz[maxn << 2];
int fen[maxn];
vector<pii> C;

void shift(int id, int l, int r);

void add(int id, int l, int r, int ql, int qr, int x){
	if(qr <= l or r <= ql)
		return;
	if(l >= ql and r <= qr){
		seg[id] += x;
		lz[id] += x;
		return;
	}
	shift(id, l, r);
	add(lc, l, mid, ql, qr, x);
	add(rc, mid, r, ql, qr, x);
	seg[id] = max(seg[lc], seg[rc]);
}

void change(int id, int l, int r, int p, int x){
	if(l + 1 == r){
		seg[id] = x;
		return;
	}
	shift(id, l, r);
	if(p < mid)
		change(lc, l, mid, p, x);
	else
		change(rc, mid, r, p, x);
	seg[id] = max(seg[lc], seg[rc]);
}

void shift(int id, int l, int r){
	if(!lz[id])
		return;
	add(lc, l, mid, l, mid, lz[id]);
	add(rc, mid, r, mid, r, lz[id]);
	lz[id] = 0;
}

void add(int i, int x){
	for(i ++; i <= m; i += i & -i)
		fen[i] += x;
}

int get(int i){
	int res = 0;
	for(; i; i -= i & -i)
		res += fen[i];
	return res;
}

int get(int l, int r){
	return get(r) - get(l);
}

void add(int x, int i, int val){
	int ind = lower_bound(all(C), mp(x, i)) - C.begin();
	int r = lower_bound(all(C), mp(x, -inf)) - C.begin();
	int l = upper_bound(all(C), mp(x, inf)) - C.begin();
	add(ind, val);
	add(1, 0, m, 0, r, val);
	if(val == -1){
		change(1, 0, m, ind, -inf);
	}
	else{
		int res = get(l, m) - (n - 1 - i);
		change(1, 0, m, ind, res);
	}
}

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 ++)
		C.pb(mp(A[i], i));
	for(int i = 0; i < q; i ++)
		C.pb(mp(V[i], X[i]));
	sort(all(C));
	C.resize(unique(all(C)) - C.begin());
	m = C.size();
	fill_n(seg, maxn << 2, -inf);
	for(int i = 0; i < n; i ++){
		a[i] = A[i];
		add(a[i], i, 1);
	}
	vector<int> ans;
	for(int i = 0; i < q; i ++){
		add(a[X[i]], X[i], -1);
		a[X[i]] = V[i];
		add(a[X[i]], X[i], 1);
		ans.pb(seg[1]);
	}
	return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40