3 files changed, 236 insertions, 0 deletions
diff --git a/18.5/dec/plat/balance.cpp b/18.5/dec/plat/balance.cpp
new file mode 100644
index 0000000..154adbe
--- /dev/null
+++ b/18.5/dec/plat/balance.cpp
@@ -0,0 +1,62 @@
+#define _CRT_SECURE_NO_WARNINGS
+#include <cstdlib>
+#include <cstdio>
+#include <iostream>
+#include <sstream>
+#include <fstream>
+#include <string>
+#include <string.h>
+#include <vector>
+#include <deque>
+#include <queue>
+#include <stack>
+#include <set>
+#include <unordered_set>
+#include <map>
+#include <unordered_map>
+#include <algorithm>
+#include <functional>
+#include <utility>
+#include <bitset>
+#include <cmath>
+#include <ctime>
+#include <climits>
+using namespace std;
+
+struct point { long long x, y; };
+
+long long F[100005];
+
+bool cw(point a, point b, point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) < 0; }
+
+int main() {
+	ifstream fin("balance.in");
+	ofstream fout("balance.out");
+
+	int N;
+	fin >> N;
+	for (int i = 0; i < N; i++) fin >> F[i + 1];
+	F[0] = F[N + 1] = 0;
+
+	vector<point> P;
+	for (int i = 0; i < N + 2; i++) P.push_back({ i, F[i] });
+
+	sort(P.begin(), P.end(), [](const point &a, const point &b) { return a.x * b.y < b.x * a.y || (a.x * b.y == b.x * a.y && a.x < b.x); });
+
+	vector<point> S;
+	S.push_back(P[0]);
+	S.push_back(P[1]);
+
+	for (int i = 2; i < N + 2; i++) {
+		while (S.size() > 1 && !cw(S[S.size() - 2], S[S.size() - 1], P[i])) S.pop_back();
+		S.push_back(P[i]);
+	}
+
+	for (int i = 0; i < S.size() - 1; i++) {
+		for (int j = 0; j < S[i + 1].x - S[i].x; j++) {
+			if (!i && !j) continue;
+			if (S[i].y < S[i + 1].y) cout << 100000 * S[i].y + (100000 * j * (S[i + 1].y - S[i].y)) / (S[i + 1].x - S[i].x) << endl;
+			else cout << 100000 * S[i + 1].y + (100000 * (S[i + 1].x - S[i].x - j) * (S[i].y - S[i + 1].y)) / (S[i + 1].x - S[i].x) << endl;
+		}
+	}
+}
+\ No newline at end of file
diff --git a/18.5/dec/plat/itout.cpp b/18.5/dec/plat/itout.cpp
new file mode 100644
index 0000000..ce77c87
--- /dev/null
+++ b/18.5/dec/plat/itout.cpp
@@ -0,0 +1,99 @@
+#include <algorithm>
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <vector>
+#include <queue>
+#include <set>
+#include <map>
+#include <unordered_set>
+#include <unordered_map>
+#include <cmath>
+#include <cstring>
+#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL)
+#define FOR(i, a, b, in) for (int i = (a); i < (b); i += in)
+#define REP(i, a, b) for (int i = (a); i < (b); i++)
+#define RFOR(i, a, b, in) for (int i = (a) - 1; i >= (b); i -= in)
+#define RREP(i, a, b) for (int i = (a) - 1; i >= (b); i--)
+#define trav(a, x) for (auto& a : x)
+#define mp make_pair
+#define pb push_back
+#define f first
+#define s second
+#define lb lower_bound
+#define ub upper_bound
+#define sz(x) (int)x.size()
+#define all(x) begin(x), end(x)
+#define rsz resize
+#define mem(a, b) memset(a, (b), sizeof(a))
+using namespace std;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd;
+typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd;
+typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd;
+constexpr auto INF = (int)1e9;
+constexpr auto LINF = (ll)1e18;
+
+int N, A[100005];
+vi ans;
+pl seg[4 * 100005];
+
+pl merge(const pl& a, const pl& b) {
+	pl ret;
+	if (a.first == b.first) ret = pl(a.first, (a.second + b.second < 0 ? LINF : a.second + b.second));
+	else ret = (a.first > b.first ? a : b);
+	return ret;
+}
+
+void update(int i, pl v, int l = 1, int r = -1, int n = 1) {
+	if (r == -1) r = N;
+	if (l == r) seg[n] = v;
+	else {
+		int m = (l + r) >> 1;
+		i <= m ? update(i, v, l, m, n << 1) : update(i, v, m + 1, r, n << 1 | 1);
+		seg[n] = merge(seg[n << 1], seg[n << 1 | 1]);
+	}
+}
+
+pl query(int a, int b, int l = 1, int r = -1, int n = 1) {
+	if (r == -1) r = N;
+	if (l > b || r < a) return pl(0, 0);
+	if (l >= a && r <= b) return seg[n];
+	int m = (l + r) >> 1;
+	return merge(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1));
+}
+
+int main() {
+	init_io("itout");
+
+	ll K;
+	cin >> N >> K;
+	for (int i = 0; i < N; i++) cin >> A[i];
+
+	for (int i = 0; i < 4 * N; i++) seg[i] = pl(0, 0);
+
+	for (int i = N - 1; i >= 0; i--) {
+		pl q = query(A[i], N);
+		if (q.first++ == 0) q.second++;
+		update(A[i], q);
+	}
+
+	int d = query(1, N).first;
+	cout << N - d << endl;
+	for (int i = 0; i < N; i++) {
+		pl q = query(A[i], A[i]);
+		if (q.first == d) {
+			if (K <= q.second) d--;
+			else {
+				ans.push_back(A[i]);
+				K -= q.second;
+			}
+		}
+		else ans.push_back(A[i]);
+	}
+
+	sort(ans.begin(), ans.end());
+	for (auto& x : ans) cout << x << endl;
+}
diff --git a/18.5/open/plat/boxes.cpp b/18.5/open/plat/boxes.cpp
new file mode 100644
index 0000000..75695b9
--- /dev/null
+++ b/18.5/open/plat/boxes.cpp
@@ -0,0 +1,75 @@
+#include <bits/stdc++.h>
+#include "grader.h"
+using namespace std;
+typedef pair<int, int> ii;
+typedef vector<int> vi;
+typedef vector<ii> vii;
+
+int d[100005], sz[100005], L[100005][20];
+ii P[100005];
+vi G[100005];
+
+void addRoad(int a, int b) {
+	G[a].push_back(b);
+	G[b].push_back(a);
+}
+
+void dfs(int u, int p) {
+	d[u] = (p != -1 ? d[p] : 0) + 1;
+	sz[u] = 1;
+	L[u][0] = p;
+	for (int i = 0; i < 16; i++) {
+		if (L[u][i] != -1) L[u][i + 1] = L[L[u][i]][i];
+	}
+	for (auto& v : G[u]) {
+		if (v != p) {
+			dfs(v, u);
+			sz[u] += sz[v];
+		}
+	}
+}
+
+int lca(int u, int v) {
+	if (d[u] > d[v]) swap(u, v);
+	for (int i = 16; i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[v][i];
+	if (u == v) return u;
+	for (int i = 16; i >= 0; i--) if (L[u][i] != -1 && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i];
+	return L[u][0];
+}
+
+int pre(int l, int u) {
+	for (int i = 16; i >= 0; i--) {
+		if (L[u][i] != -1 && d[L[u][i]] > d[l]) u = L[u][i];
+	}
+	return u;
+}
+
+void solve(int u, int p, int x, int y) {
+	P[u] = ii(x, y);
+	setFarmLocation(u, x, y);
+	y += sz[u];
+	for (auto& v : G[u]) {
+		if (v != p) {
+			y -= sz[v];
+			solve(v, u, x, y);
+			x += sz[v];
+		}
+	}
+}
+
+void buildFarms() {
+	memset(L, -1, sizeof(L));
+	dfs(0, -1);
+	solve(0, -1, 1, 1);
+}
+
+void notifyFJ(int a, int b) {
+	if (a == b) addBox(P[a].first, P[a].second, P[a].first, P[a].second);
+	else {
+		int u = lca(a, b);
+		int v = pre(u, (a != u ? a : b));
+		if (a != u) swap(u, v);
+		addBox(P[u].first, P[u].second, P[a].first, P[a].second);
+		addBox(P[v].first, P[v].second, P[b].first, P[b].second);
+	}
+}