oj.uz

Submission #676326

# Submission time Handle Problem Language Result Execution time Memory
676326 2022-12-30T10:43:19 Z ghostwriter Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 2089 ms 71096 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 23 ms 724 KB Output is correct
3 Correct 90 ms 884 KB Output is correct
4 Correct 93 ms 888 KB Output is correct
5 Correct 87 ms 852 KB Output is correct
6 Correct 72 ms 896 KB Output is correct
7 Correct 78 ms 884 KB Output is correct
8 Correct 83 ms 908 KB Output is correct
9 Correct 90 ms 1000 KB Output is correct
10 Correct 78 ms 996 KB Output is correct
11 Correct 76 ms 872 KB Output is correct
12 Correct 81 ms 872 KB Output is correct
13 Correct 75 ms 980 KB Output is correct
14 Correct 76 ms 872 KB Output is correct
15 Correct 80 ms 980 KB Output is correct
16 Correct 74 ms 852 KB Output is correct
17 Correct 78 ms 988 KB Output is correct
18 Correct 90 ms 864 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 23 ms 724 KB Output is correct
3 Correct 90 ms 884 KB Output is correct
4 Correct 93 ms 888 KB Output is correct
5 Correct 87 ms 852 KB Output is correct
6 Correct 72 ms 896 KB Output is correct
7 Correct 78 ms 884 KB Output is correct
8 Correct 83 ms 908 KB Output is correct
9 Correct 90 ms 1000 KB Output is correct
10 Correct 78 ms 996 KB Output is correct
11 Correct 76 ms 872 KB Output is correct
12 Correct 81 ms 872 KB Output is correct
13 Correct 75 ms 980 KB Output is correct
14 Correct 76 ms 872 KB Output is correct
15 Correct 80 ms 980 KB Output is correct
16 Correct 74 ms 852 KB Output is correct
17 Correct 78 ms 988 KB Output is correct
18 Correct 90 ms 864 KB Output is correct
19 Correct 1097 ms 1524 KB Output is correct
20 Correct 1461 ms 1684 KB Output is correct
21 Correct 1142 ms 1732 KB Output is correct
22 Correct 1377 ms 1696 KB Output is correct
23 Correct 1102 ms 1556 KB Output is correct
24 Correct 1119 ms 1536 KB Output is correct
25 Correct 1097 ms 1624 KB Output is correct
26 Correct 1112 ms 1760 KB Output is correct
27 Correct 1073 ms 1664 KB Output is correct
28 Correct 1072 ms 1612 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2488 KB Output is correct
2 Correct 89 ms 4652 KB Output is correct
3 Correct 159 ms 7348 KB Output is correct
4 Correct 142 ms 7264 KB Output is correct
5 Correct 137 ms 7224 KB Output is correct
6 Correct 142 ms 7364 KB Output is correct
7 Correct 138 ms 7232 KB Output is correct
8 Correct 139 ms 7288 KB Output is correct
9 Correct 135 ms 7228 KB Output is correct
10 Correct 126 ms 7312 KB Output is correct
11 Correct 120 ms 7268 KB Output is correct
12 Correct 128 ms 7312 KB Output is correct
13 Correct 129 ms 7300 KB Output is correct
14 Correct 123 ms 7304 KB Output is correct
15 Correct 118 ms 7292 KB Output is correct
16 Correct 125 ms 7204 KB Output is correct
17 Correct 118 ms 7196 KB Output is correct
18 Correct 122 ms 7288 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 724 KB Output is correct
2 Correct 23 ms 724 KB Output is correct
3 Correct 90 ms 884 KB Output is correct
4 Correct 93 ms 888 KB Output is correct
5 Correct 87 ms 852 KB Output is correct
6 Correct 72 ms 896 KB Output is correct
7 Correct 78 ms 884 KB Output is correct
8 Correct 83 ms 908 KB Output is correct
9 Correct 90 ms 1000 KB Output is correct
10 Correct 78 ms 996 KB Output is correct
11 Correct 76 ms 872 KB Output is correct
12 Correct 81 ms 872 KB Output is correct
13 Correct 75 ms 980 KB Output is correct
14 Correct 76 ms 872 KB Output is correct
15 Correct 80 ms 980 KB Output is correct
16 Correct 74 ms 852 KB Output is correct
17 Correct 78 ms 988 KB Output is correct
18 Correct 90 ms 864 KB Output is correct
19 Correct 1097 ms 1524 KB Output is correct
20 Correct 1461 ms 1684 KB Output is correct
21 Correct 1142 ms 1732 KB Output is correct
22 Correct 1377 ms 1696 KB Output is correct
23 Correct 1102 ms 1556 KB Output is correct
24 Correct 1119 ms 1536 KB Output is correct
25 Correct 1097 ms 1624 KB Output is correct
26 Correct 1112 ms 1760 KB Output is correct
27 Correct 1073 ms 1664 KB Output is correct
28 Correct 1072 ms 1612 KB Output is correct
29 Correct 29 ms 2488 KB Output is correct
30 Correct 89 ms 4652 KB Output is correct
31 Correct 159 ms 7348 KB Output is correct
32 Correct 142 ms 7264 KB Output is correct
33 Correct 137 ms 7224 KB Output is correct
34 Correct 142 ms 7364 KB Output is correct
35 Correct 138 ms 7232 KB Output is correct
36 Correct 139 ms 7288 KB Output is correct
37 Correct 135 ms 7228 KB Output is correct
38 Correct 126 ms 7312 KB Output is correct
39 Correct 120 ms 7268 KB Output is correct
40 Correct 128 ms 7312 KB Output is correct
41 Correct 129 ms 7300 KB Output is correct
42 Correct 123 ms 7304 KB Output is correct
43 Correct 118 ms 7292 KB Output is correct
44 Correct 125 ms 7204 KB Output is correct
45 Correct 118 ms 7196 KB Output is correct
46 Correct 122 ms 7288 KB Output is correct
47 Correct 503 ms 22020 KB Output is correct
48 Correct 1892 ms 65996 KB Output is correct
49 Correct 2089 ms 70900 KB Output is correct
50 Correct 2084 ms 70856 KB Output is correct
51 Correct 2068 ms 70856 KB Output is correct
52 Correct 2068 ms 70808 KB Output is correct
53 Correct 2065 ms 70856 KB Output is correct
54 Correct 1889 ms 71096 KB Output is correct
55 Correct 2001 ms 70992 KB Output is correct
56 Correct 1893 ms 71064 KB Output is correct
57 Correct 1980 ms 71020 KB Output is correct
58 Correct 1888 ms 70940 KB Output is correct
59 Correct 1734 ms 69696 KB Output is correct
60 Correct 1760 ms 69760 KB Output is correct
61 Correct 1725 ms 69640 KB Output is correct
62 Correct 1728 ms 69480 KB Output is correct
63 Correct 1672 ms 69480 KB Output is correct
64 Correct 1691 ms 69448 KB Output is correct
65 Correct 1586 ms 69340 KB Output is correct
66 Correct 1557 ms 69344 KB Output is correct
67 Correct 1584 ms 69344 KB Output is correct