Submission #676326

#	Time	Username	Problem	Language	Result	Execution time	Memory
676326		ghostwriter	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2089 ms	71096 KiB

bubblesort2

#include "bubblesort2.h"
// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
	#include "grader.cpp"
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
namespace subtask12 {
	const int MAXN = 16000;
	int N, Q;
	vi A, X, V, d[MAXN];
	bool checkCondition(vi A, vi X, vi V) {
		subtask12::A = A;
		subtask12::X = X;
		subtask12::V = V;
		return sz(A) <= 8000 && sz(X) <= 8000;
	}
	void compress() {
		vi A1;
		EACH(i, A) A1.pb(i);
		EACH(i, V) A1.pb(i);
		sort(all(A1));
		EACH(i, A) i = lb(all(A1), i) - A1.bg();
		EACH(i, V) i = lb(all(A1), i) - A1.bg();
	}
	int solve() {
		int rs = 0, maxx = -1, num = N;
		FRN(i, N) d[A[i]].pb(i);
		FRN(i, MAXN) {
			if (d[i].empty()) continue;
			EACH(j, d[i]) {
				rs = max(rs, num - N + max(maxx, j));
				--num;
				maxx = max(maxx, j + 1);
			}
			d[i].clear();
		}
		return rs;
	}
	vi countScans() {
		N = sz(A);
		Q = sz(X);
		compress();
		vi ANS(Q);
		FRN(j, Q) {
			A[X[j]] = V[j];
			ANS[j] = solve();
		}
		return ANS;
	}
}
namespace subtask34 {
	/*
		This problem is tough, JOI is tough :(. I've had some beautiful formular to solve subtask1 and subtask2 but not the problem.
		The idea is quite simple though: Consider any element i, let S[i] be the number of element to the left of i and bigger than a[i].
		Answer must be at least S[i] for all i and yes Max(S[i]) for 1 <= i <= n is the answer we need to get in a query because after S[i]
		iteration, any element that occure before i must not exceed a[i]. Now we tried to transform the formular into something more elegant.
		Consider i that has max S[i], if there'is any element j > i and a[j] <= i then we consider j instead of i because S[j] will be at least S[i]
		(pretty obvious because every element bigger than a[i] is bigger than a[j] and j is on the right of i) and do this until you can't shift it
		no more. If we consider i - cnt[i] instead of S[i] (cnt[i] is the number of element <= a[i]) then at the position i, S[i] = i - cnt[i] = ans as we
		shift it as far as we could. Every other position has i - cnt[i] <= S[i] (as we can minus some extra element). So max(i - cnt[i]) = max(S[i]) as
		there is at least one position that has i - cnt[i] = max(S[i]) and every other position has i - cnt[i] <= S[i]. We have transform the problem
		into a elegant and well known lazy propagate query?
	*/
	const int oo = 1e9 + 5;
	const int MAXN = 1e6 + 5;
	const int T = 4e6 + 5;
	int N, Q, tr[T], la[T];
	vpi A1;
	void lazy(int i) {
		if (!la[i]) return;
		tr[i] += la[i];
		if (i * 2 + 1 < T) {
			la[i * 2] += la[i];
			la[i * 2 + 1] += la[i];
		}
		la[i] = 0;
	}
	void upd(int i, int l, int r, int ql, int qr, int v) {
		lazy(i);
		if (r < ql || l > qr) return;
		if (ql <= l && r <= qr) {
			la[i] += v;
			lazy(i);
			return;
		}
		int mid = l + (r - l) / 2;
		upd(i * 2, l, mid, ql, qr, v);
		upd(i * 2 + 1, mid + 1, r, ql, qr, v);
		tr[i] = max(tr[i * 2], tr[i * 2 + 1]);
	}
	void upd(int l, int r, int v) { upd(1, 0, MAXN - 1, l, r, v); }
	int get(int i, int l, int r, int ql, int qr) {
		lazy(i);
		if (r < ql || l > qr) return -oo;
		if (ql <= l && r <= qr) return tr[i];
		int mid = l + (r - l) / 2;
		return max(get(i * 2, l, mid, ql, qr), get(i * 2 + 1, mid + 1, r, ql, qr));
	}
	int get(int l, int r) { return get(1, 0, MAXN - 1, l, r); }
	int getp(pi v) { return lb(all(A1), v) - A1.bg(); }
	vi countScans(vi A, vi X, vi V) {
		N = sz(A);
		Q = sz(X);
		FRN(i, N) A1.pb({A[i], i});
		FRN(i, Q) A1.pb({V[i], X[i]});
		sort(all(A1));
		FRN(i, N) {
			int cur = getp({A[i], i});
			upd(cur, MAXN - 1, -1);
			upd(cur, cur, i + 1);
		}
		vi ANS(Q);
		FRN(i, Q) {
			int pos = X[i], v = V[i];
			int cur = getp({A[pos], pos}), nxt = getp({v, pos});
			upd(cur, cur, -pos - 1);
			upd(cur, MAXN - 1, 1);
			upd(nxt, MAXN - 1, -1);
			upd(nxt, nxt, pos + 1);
			ANS[i] = get(0, MAXN - 1);
			A[pos] = v;
		}
		return ANS;
	}
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	if (subtask12::checkCondition(A, X, V)) return subtask12::countScans();
	return subtask34::countScans(A, X, V);
}
/*
4 2
1 2 3 4
0 3
2 1

4 1
1 2 3 4
0 3
*/

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