Submission #99324

#	Time	Username	Problem	Language	Result	Execution time	Memory
99324		youngyojun	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	3372 ms	66844 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const int MAXN = 500055;
const int MAXQ = 500055;
const int MAXC = MAXN+MAXQ;

struct SEG {
	SEG() { init(); }
	int ds[MAXC*4], dmx[MAXC*4];

	void init() {
		fill(dmx, dmx+MAXC*4, -INF);
	}

	void prop(int i, int s, int e) {
		if(!ds[i]) return;
		if(s != e) {
			ds[i<<1] += ds[i];
			ds[i<<1|1] += ds[i];
		}
		dmx[i] += ds[i];
		ds[i] = 0;
	}
	void cal(int i) {
		dmx[i] = max(dmx[i<<1], dmx[i<<1|1]);
	}

	void upd(int i, int s, int e, int p, int q, int r) {
		prop(i, s, e);
		if(q < p || e < p || q < s) return;
		if(p <= s && e <= q) {
			ds[i] += r;
			prop(i, s, e);
			return;
		}
		int m = (s+e) >> 1;
		upd(i<<1, s, m, p, q, r);
		upd(i<<1|1, m+1, e, p, q, r);
		cal(i);
	}
	int get() { return dmx[1]; }
} seg;

vector<pii> PV;
int A[MAXN], B[MAXQ], C[MAXQ];

int Ans[MAXQ];
int N, Q, L;

void solve() {
	for(int i = 0; i < N; i++) PV.eb(A[i], i);
	for(int i = 0; i < Q; i++) PV.eb(B[i], C[i]);
	sorv(PV); univ(PV);
	L = sz(PV);

	for(int i = 0, j; i < N; i++) {
		j = int(lower_bound(allv(PV), pii(A[i], i)) - PV.begin());
		seg.upd(1, 0, L-1, j, j, INF+i);
		seg.upd(1, 0, L-1, j+1, L-1, -1);
		A[i] = j;
	}
	for(int i = 0, j, k; i < Q; i++) {
		j = int(lower_bound(allv(PV), pii(B[i], C[i])) - PV.begin());
		k = A[C[i]];
		seg.upd(1, 0, L-1, k, k, -INF-C[i]);
		seg.upd(1, 0, L-1, k+1, L-1, 1);
		seg.upd(1, 0, L-1, j, j, INF+C[i]);
		seg.upd(1, 0, L-1, j+1, L-1, -1);
		A[C[i]] = j;
		Ans[i] = seg.get();
	}
}

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
	::N = sz(A); ::Q = sz(X);
	for(int i = 0; i < N; i++) ::A[i] = A[i];
	for(int i = 0; i < Q; i++) {
		::C[i] = X[i];
		::B[i] = V[i];
	}
	solve();
	vector<int> ret(Q);
	for(int i = 0; i < Q; i++) ret[i] = Ans[i];
	return ret;
}

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