제출 #1287990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287990		KickingKun	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	7222 ms	127684 KiB

bubblesort2

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

template <class T> bool minimize(T &a, T b) {
	if (a > b) return a = b, true;
	return false;
}

template <class T> bool maximize(T &a, T b) {
	if (a < b) return a = b, true;
	return false;
}

const int N = 5e5 + 2;

int n, q;
int a[N], x[N], v[N];

namespace sub2 {
	vector <int> solve() {
		vector <int> res;
		for (int _ = 0; _ < q; _++) {
			a[x[_]] = v[_];

			vector <int> b(a, a + n + 1); 
			sort (b.begin() + 1, b.end());
			int ans = 0;
			for (int i = 1; i <= n; i++) {
				int k = upper_bound(b.begin() + 1, b.end(), a[i]) - b.begin() - 1;
				maximize(ans, i - k);
			}
			res.emplace_back(ans);
		}
		return res;
	}
}

namespace sub3 {
	set <int> pos[102];
	vector <int> solve() {
		for (int i = 1; i <= 100; i++) pos[i].clear();
		for (int i = 1; i <= n; i++) pos[a[i]].emplace(i);

		vector <int> res;
		for (int _ = 0; _ < q; _++) {
			pos[a[x[_]]].erase(x[_]);
			a[x[_]] = v[_];
			pos[a[x[_]]].emplace(x[_]);

			int ans = 0, cnt = 0;
			for (int i = 1; i <= 100; i++) if (!pos[i].empty()) {
				cnt += pos[i].size();
				maximize(ans, *pos[i].rbegin() - cnt);
			}
			res.emplace_back(ans);
		}
		return res;
	}
}

namespace sub4 {
	struct SegmentTree {
		vector <int> st, lazy;
		SegmentTree () {}
		SegmentTree (int len) {
			st.assign(len * 4 + 1, 0);
			lazy.assign(len * 4 + 1, 0);
		}

		void push_down(int id) {
			int k = lazy[id]; lazy[id] = 0;
			st[id << 1] += k; lazy[id << 1] += k;
			st[id << 1 | 1] += k; lazy[id << 1 | 1] += k;
		}

		void update(int id, int l, int r, int u, int v, int val) {
			if (u > r || v < l) return;
			if (u <= l && r <= v) {
				st[id] += val;
				lazy[id] += val;
				return;
			}
			int mid = (l + r) >> 1; push_down(id);
			update(id << 1, l, mid, u, v, val);
			update(id << 1 | 1, mid + 1, r, u, v, val);
			st[id] = max(st[id << 1], st[id << 1 | 1]);
		}

		int getMax(int l, int r) {
			return st[1];
		}
	} ST;

	set <int> pos[N << 1];

	int sz;

	void add(int val, int p) {
		int maP = (pos[val].empty() ? 0 : *pos[val].rbegin());
		pos[val].emplace(p);

		if (maP < p) ST.update(1, 1, sz, val, val, p - maP);
		ST.update(1, 1, sz, val, sz, -1);
	}

	void remove(int val, int p) {
		int maP = *pos[val].rbegin();
		pos[val].erase(p);

		if (pos[val].empty() || maP == p) {
			int ma2 = (pos[val].empty() ? 0 : *pos[val].rbegin());
			ST.update(1, 1, sz, val, val, ma2 - maP);
		}
		ST.update(1, 1, sz, val, sz, +1);
	}

	vector <int> solve() {
		vector <int> cmp;
		for (int i = 1; i <= n; i++) cmp.emplace_back(a[i]);
		for (int i = 0; i < q; i++) cmp.emplace_back(v[i]);
		sort (cmp.begin(), cmp.end()); 
		cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());

		for (int i = 1; i <= n; i++) 
			a[i] = upper_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
		for (int i = 0; i < q; i++)
			v[i] = upper_bound(cmp.begin(), cmp.end(), v[i]) - cmp.begin();

		sz = cmp.size();
		ST = SegmentTree(sz);
		for (int i = 1; i <= sz; i++) pos[i].clear();

		vector <int> res;
		for (int i = 1; i <= n; i++) add(a[i], i);

		for (int i = 0; i < q; i++) {
			remove(a[x[i]], x[i]);
			a[x[i]] = v[i];
			add(a[x[i]], x[i]);
			res.emplace_back(ST.getMax(1, sz));
		}
		return res;
	}
}

vector <int> countScans(vector <int> A,vector <int> X, vector <int> V){
	n = A.size(); q = X.size();
	for (int i = 1; i <= n; i++) a[i] = A[i - 1];
	for (int i = 0; i < q; i++) x[i] = X[i] + 1, v[i] = V[i];

	if (max(A.size(), X.size()) <= 8e3) return sub2::solve();
	if (max(*max_element(A.begin(), A.end()), *max_element(V.begin(), V.end())) <= 100)
		return sub3::solve();
	return sub4::solve();
}

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