제출 #380924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380924		qwerty234	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	29 ms	2168 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;
const int MAXN = 1e6 + 10, inf = 1e9, inff = 1e7;

int t[4 * MAXN], add[4 * MAXN], m;
vector <set<int>> s;

void build(int v, int tl, int tr) {
	add[v] = inf;
	t[v] = 0;
	if (tl == tr)
		return;
	int tm = (tl + tr)>>1;
	build((v << 1), tl, tm);
	build(((v << 1)|1), tm + 1, tr);
}

void push(int v, int tl, int tr) {
	if (tl == tr || add[v] == inf)
		return;
	t[(v << 1)] += add[v];
	t[((v << 1)|1)] += add[v];
	if (add[(v << 1)] == inf)
		add[(v << 1)] = add[v];
	else
		add[(v << 1)] += add[v];
	if (add[((v << 1)|1)] == inf)
		add[((v << 1)|1)] = add[v];
	else
		add[((v << 1)|1)] += add[v];
	add[v] = inf;
}

void upd(int v, int tl, int tr, int l, int r, int val) {
	if (r < tl || tr < l)
		return;
	if (l <= tl && tr <= r) {
		t[v] += val;
		if (add[v] == inf)
			add[v] = val;
		else
			add[v] += val;
		return;
	}
	int tm = (tl + tr)>>1;
	push(v, tl, tr);
	upd((v << 1), tl, tm, l, r, val);
	upd(((v << 1)|1), tm + 1, tr, l, r, val);
	t[v] = max(t[(v << 1)], t[((v << 1)|1)]);
}

int get(int v, int tl, int tr, int l, int r) {
	if (r < tl || tr < l)
		return -inff;
	push(v, tl, tr);
	if (l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr)>>1;
	return max(get((v << 1), tl, tm, l, r), get(((v << 1)|1), tm + 1, tr, l, r));
}

void addd(int i, int x) {
	int mx1 = -*s[x].begin();
	s[x].insert(-i);
	int mx2 = -*s[x].begin();
	upd(1, 0, m - 1, x, x, -mx1 + mx2);
	upd(1, 0, m - 1, x + 1, m - 1, -1);
}

void del(int i, int x) {
	int mx1 = -*s[x].begin();
	s[x].erase(-i);
	int mx2 = -*s[x].begin();
	upd(1, 0, m - 1, x, x, -mx1 + mx2);
	upd(1, 0, m - 1, x + 1, m - 1, 1);
}

vector <int> countScans(vector <int> a, vector <int> x, vector <int> v) {
	int n = a.size(), q = x.size();
	vector <int> ar = {};
	for (int i = 0; i < n; i++) ar.pb(a[i]);
	for (int i = 0; i < q; i++) ar.pb(v[i]);
	sort(ar.begin(), ar.end());
	m = unique(ar.begin(), ar.end()) - ar.begin();
	for (int i = 0; i < n; i++)
		a[i] = lower_bound(ar.begin(), ar.begin() + m, a[i]) - ar.begin();
	for (int i = 0; i < q; i++)
		v[i] = lower_bound(ar.begin(), ar.begin() + m, v[i]) - ar.begin();
	build(1, 0, m - 1);
	ar.clear();
	for (int i = 0; i < n; i++) ar.pb(a[i]);
	sort(ar.begin(), ar.end());
	s.resize(m);
	for (int i = 0; i < m; i++) {
		s[i].clear();
		s[i].insert(inff);
	}
	for (int i = 0; i < m; i++)
		upd(1, 0, m - 1, i, i, -*s[i].begin());
	for (int i = 0; i < n; i++)
		addd(i, a[i]);
	vector <int> ans;
	for (int i = 0; i < q; i++) {
		del(x[i], a[i]);
		addd(x[i], v[i]);
		a[x[i]] = v[i];
		ans.pb(get(1, 0, m - 1, 0, m - 1));
	}
	return ans;
}

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