Submission #67499

#	Time	Username	Problem	Language	Result	Execution time	Memory
67499		aome	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2902 ms	77016 KiB

bubblesort2

#include "bubblesort2.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int INF = 0x3f3f3f;

struct SegmentTree {
	int Tmax[N << 3];
	int Tcnt[N << 3];
	int lazy[N << 3];

	SegmentTree() {
		memset(Tmax, -INF, sizeof Tmax);
	}

	void push(int i, int l, int r) {
		Tmax[i] += lazy[i];
		if (l != r) {
			lazy[i << 1] += lazy[i], lazy[i << 1 | 1] += lazy[i];
		}
		lazy[i] = 0;
	}

	#define mid ((l + r) >> 1)

	void updRange(int i, int l, int r, int L, int R, int x) {
		push(i, l, r);
		if (l > R || L > r) return;
		if (L <= l && r <= R) {
			lazy[i] = x, push(i, l, r); return;
		}
		updRange(i << 1, l, mid, L, R, x);
		updRange(i << 1 | 1, mid + 1, r, L, R, x);
		Tmax[i] = max(Tmax[i << 1], Tmax[i << 1 | 1]);
	}

	void updPos(int i, int l, int r, int p, int x, int y) {
		push(i, l, r);
		if (p > r || l > p) return;
		if (l == r) { Tmax[i] = x, Tcnt[i] = y; return; }
		updPos(i << 1, l, mid, p, x, y);
		updPos(i << 1 | 1, mid + 1, r, p, x, y);
		Tcnt[i] = Tcnt[i << 1] + Tcnt[i << 1 | 1];
		Tmax[i] = max(Tmax[i << 1], Tmax[i << 1 | 1]);
	}

	int get(int i, int l, int r, int L, int R) {
		if (l > R || L > r) return 0;
		if (L <= l && r <= R) return Tcnt[i];
		return get(i << 1, l, mid, L, R) + get(i << 1 | 1, mid + 1, r, L, R);
	}

	#undef mid
} IT;

struct Data {
	int v, p, id;

	bool operator < (const Data& rhs) const {
		return v == rhs.v ? p < rhs.p : v < rhs.v;
	}
};	

int prv[N], pos[N];
vector<Data> vec;

vector<int> countScans(vector<int> a, vector<int> x, vector<int> y) {
	int n = a.size(), m = x.size();
	for (int i = 0; i < n; ++i) vec.push_back({a[i], i, i});
	for (int i = 0; i < m; ++i) vec.push_back({y[i], x[i], i + n});
	sort(vec.begin(), vec.end());
	int sz = n + m;
	for (int i = 0; i < sz; ++i) {
		if (vec[i].id >= n) {
			pos[vec[i].id - n] = i; continue;
		}
		int F = vec[i].p - IT.get(1, 0, sz - 1, 0, i);
		IT.updPos(1, 0, sz - 1, i, F, 1), prv[vec[i].p] = i;
	}
	vector<int> res;
	for (int i = 0; i < m; ++i) {
		int &tmp = prv[x[i]];
		IT.updRange(1, 0, sz - 1, tmp, sz - 1, 1);
		IT.updPos(1, 0, sz - 1, tmp, -INF, 0);
		tmp = pos[i];
		int F = x[i] - IT.get(1, 0, sz - 1, 0, tmp);
		IT.updRange(1, 0, sz - 1, tmp, sz - 1, -1);
		IT.updPos(1, 0, sz - 1, tmp, F, 1);
		res.push_back(IT.Tmax[1]);
	}
	return res;
}

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