Restructure directories AGAIN so contests from the same season are in the same directory

15 files changed, 943 insertions, 0 deletions

diff --git a/19.5/dec/gold/cowmbat.cpp b/19.5/dec/gold/cowmbat.cpp
new file mode 100644
index 0000000..e224936
--- /dev/null
+++ b/19.5/dec/gold/cowmbat.cpp
@@ -0,0 +1,48 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+ll a[30][30], cost[100001][30] = { 0 }, DP[100001][30];
+
+int main() {
+	ifstream cin("cowmbat.in");
+	ofstream cout("cowmbat.out");
+
+	int N, M, K;
+	string S;
+	cin >> N >> M >> K >> S;
+	for (int i = 0; i <= 26; ++i) {
+		for (int j = 0; j <= 26; ++j) a[i][j] = 1e9;
+	}
+	for (int i = 0; i < M; ++i) {
+		for (int j = 0; j < M; ++j) cin >> a[i][j];
+	}
+
+	for (int k = 0; k < M; ++k) {
+		for (int i = 0; i < M; ++i) {
+			for (int j = 0; j < M; ++j) a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
+		}
+	}
+
+	for (int i = 0; i < K; ++i) {
+		for (int j = 0; j <= 26; ++j) cost[0][j] += a[S[i] - 'a'][j];
+	}
+	for (int i = 0; i < N - K; ++i) {
+		for (int j = 0; j <= 26; ++j) {
+			cost[i + 1][j] = a[S[i + K] - 'a'][j] - a[S[i] - 'a'][j] + cost[i][j];
+		}
+	}
+
+	for (int i = 0; i <= N; ++i) {
+		for (int j = 0; j <= 26; ++j) DP[i][j] = 1e9;
+	}
+	DP[0][26] = 0;
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j <= 26; ++j) DP[i + 1][j] = min(a[S[i] - 'a'][j] + DP[i][j], DP[i + 1][j]);
+		int best = *min_element(DP[i], DP[i] + 27);
+		if (i + K <= N) {
+			for (int j = 0; j <= 26; ++j) DP[i + K][j] = min(best + cost[i][j], DP[i + K][j]);
+		}
+	}
+	cout << *min_element(DP[N], DP[N] + 27);
+}
diff --git a/19.5/dec/gold/milkvisits.cpp b/19.5/dec/gold/milkvisits.cpp
new file mode 100644
index 0000000..d02c1bc
--- /dev/null
+++ b/19.5/dec/gold/milkvisits.cpp
@@ -0,0 +1,70 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+
+int N, M, T[100001], d[100001] = { 0 }, L[100001][20];
+vector<int> G[100001];
+bitset<100001> ans;
+pair<ii, int> q[100001];
+unordered_set<int> x[100001], y[100001];
+
+void dfs(int u, int p) {
+	d[u] = d[p] + 1;
+	L[u][0] = p;
+	for (int i = 0; i < 18 && L[u][i]; i++) L[u][i + 1] = L[L[u][i]][i];
+	for (auto& v : G[u]) if (v != p) dfs(v, u);
+}
+
+int lca(int u, int v) {
+	if (d[u] > d[v]) swap(u, v);
+	for (int i = 18; i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[v][i];
+	if (u == v) return u;
+	for (int i = 18; i >= 0; i--) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i];
+	return L[u][0];
+}
+
+void solve(int u, int p, unordered_map<int, unordered_set<int>>& S) {
+	for (auto& v : G[u]) {
+		if (v != p) {
+			unordered_map<int, unordered_set<int>> tmp;
+			solve(v, u, tmp);
+			if (tmp.size() > S.size()) swap(tmp, S);
+			for (auto& x : tmp) {
+				for (auto& i : x.s) S[x.f].insert(i);
+			}
+		}
+	}
+	for (auto& i : x[u]) S[q[i].s].insert(i);
+	for (auto& i : S[T[u]]) ans[i] = 1;
+	S[T[u]].clear();
+	for (auto& i : y[u]) {
+		if (S[q[i].s].find(i) != S[q[i].s].end()) S[q[i].s].erase(i);
+	}
+}
+
+int main() {
+	ifstream cin("milkvisits.in");
+	ofstream cout("milkvisits.out");
+	
+	cin >> N >> M;
+	for (int i = 1; i <= N; i++) cin >> T[i];
+	for (int i = 1; i < N; i++) {
+		int u, v;
+		cin >> u >> v;
+		G[u].push_back(v), G[v].push_back(u);
+	}
+	dfs(1, 0);
+	for (int i = 0; i < M; i++) {
+		int a, b, c;
+		cin >> a >> b >> c;
+		q[i] = { ii(a, b), c };
+		int l = lca(a, b);
+		if (a != l) x[a].insert(i), y[l].insert(i);
+		if (b != l) x[b].insert(i), y[l].insert(i);
+	}
+	unordered_map<int, unordered_set<int>> S;
+	solve(1, 0, S);
+	for (int i = 0; i < M; i++) cout << (ans[i] || T[q[i].f.f] == q[i].s || T[q[i].f.s] == q[i].s);
+}
diff --git a/19.5/dec/gold/pump.cpp b/19.5/dec/gold/pump.cpp
new file mode 100644
index 0000000..20beb76
--- /dev/null
+++ b/19.5/dec/gold/pump.cpp
@@ -0,0 +1,46 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+typedef vector<int> vi;
+typedef vector<ii> vii;
+constexpr int INF = 1e9;
+
+vector<pair<int, ii>> G[1001];
+
+int main() {
+	ifstream cin("pump.in");
+	ofstream cout("pump.out");
+
+	int N, M;
+	cin >> N >> M;
+	while (M--) {
+		int a, b, c, f;
+		cin >> a >> b >> c >> f;
+		G[a].emplace_back(b, ii(c, f));
+		G[b].emplace_back(a, ii(c, f));
+	}
+
+	int ans = 0;
+	for (int i = 1; i <= 1000; ++i) {
+		vi dist(N + 1, INF);
+		dist[1] = 0;
+		priority_queue<ii, vii, greater<ii>> pq;
+		pq.emplace(0, 1);
+		while (!pq.empty()) {
+			int d = pq.top().f, u = pq.top().s;
+			pq.pop();
+			if (d > dist[u]) continue;
+			for (auto& v : G[u]) {
+				if (v.s.s >= i && d + v.s.f < dist[v.f]) {
+					dist[v.f] = d + v.s.f;
+					pq.emplace(dist[v.f], v.f);
+				}
+			}
+		}
+		ans = max((int)1e6 * i / dist[N], ans);
+	}
+	cout << ans << '\n';
+}
diff --git a/19.5/dec/plat/snowcow.cpp b/19.5/dec/plat/snowcow.cpp
new file mode 100644
index 0000000..b4df8bd
--- /dev/null
+++ b/19.5/dec/plat/snowcow.cpp
@@ -0,0 +1,127 @@
+#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 io(s) if (fopen(((string)s+".in").c_str(), "r")) { freopen(((string)s+".in").c_str(), "r", stdin); freopen(((string)s+".out").c_str(), "w", stdout); } 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;
+
+const int C = 1e5;
+
+int N, cnt = 0, L[100005], R[100005];
+ll seg[400005] = { 0 }, tmp[400005] = { 0 };
+vector<int> G[100005];
+set<ii> S[100005];
+
+void pull(int n) { seg[n] = seg[n << 1] + seg[n << 1 | 1]; }
+void push(int l, int r, int n) {
+	seg[n] += (r - l + 1) * tmp[n];
+	if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n];
+	tmp[n] = 0;
+}
+void update(int a, int b, ll v, int l = 1, int r = -1, int n = 1) {
+	if (r == -1) r = N;
+	push(l, r, n);
+	if (l > b || r < a) return;
+	if (l >= a && r <= b) {
+		tmp[n] += v;
+		push(l, r, n);
+	}
+	else {
+		int m = (l + r) >> 1;
+		update(a, b, v, l, m, n << 1), update(a, b, v, m + 1, r, n << 1 | 1);
+		pull(n);
+	}
+}
+ll query(int a, int b, int l = 1, int r = -1, int n = 1) {
+	if (r == -1) r = N;
+	if (a > b || l > b || r < a) return 0;
+	push(l, r, n);
+	if (l >= a && r <= b) return seg[n];
+	int m = (l + r) >> 1;
+	return query(a, b, l, m, n << 1) + query(a, b, m + 1, r, n << 1 | 1);
+}
+
+void dfs(int u, int p) {
+	L[u] = ++cnt;
+	for (auto& v : G[u]) if (v != p) dfs(v, u);
+	R[u] = cnt;
+}
+
+int main() {
+	io("snowcow");
+
+	int Q;
+	cin >> N >> Q;
+	for (int i = 1; i < N; i++) {
+		int a, b;
+		cin >> a >> b;
+		G[a].push_back(b);
+		G[b].push_back(a);
+	}
+
+	dfs(1, 0);
+
+	for (int i = 1; i <= C; i++) S[i].emplace(0, 0);
+
+	while (Q--) {
+		int t;
+		cin >> t;
+		if (t == 1) {
+			int x, c;
+			cin >> x >> c;
+			int l = L[x], r = R[x];
+			auto it = --S[c].lower_bound(ii(L[x], L[x])); // Get leftmost interval
+			while (it != S[c].lower_bound(ii(R[x] + 1, R[x] + 1))) {
+				update(max(it->s + 1, L[x]), min(next(it) != S[c].end() ? next(it)->f - 1 : N, R[x]), 1); // Update range between intervals
+				if (it->s >= L[x] - 1) {
+					l = min(it->f, l);
+					r = max(it->s, r);
+					it = S[c].erase(it); // Remove covered intervals
+				}
+				else it++;
+			}
+			if (it != S[c].end() && it->f <= R[x] + 1) {
+				l = min(it->f, l);
+				r = max(it->s, r);
+				S[c].erase(it);
+			}
+			S[c].emplace(l, r); // Add interval
+		}
+		else {
+			int x;
+			cin >> x;
+			cout << query(L[x], R[x]) << '\n';
+		}
+	}
+}
diff --git a/19.5/feb/gold/deleg.cpp b/19.5/feb/gold/deleg.cpp
new file mode 100644
index 0000000..ee9144f
--- /dev/null
+++ b/19.5/feb/gold/deleg.cpp
@@ -0,0 +1,66 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+
+int d[100001] = { 0 };
+vector<ii> G[100001];
+
+ii dfs(int u, int p) {
+	d[u] = d[p] + 1;
+	vector<ii> tmp;
+	for (auto& x : G[u]) {
+		if (!d[x.f] || d[x.f] > d[u]) tmp.push_back(x);
+	}
+	swap(G[u], tmp);
+	if (G[u].size() == 1) {
+		G[u][0] = dfs(G[u][0].f, u);
+		return ii(G[u][0].f, G[u][0].s + 1);
+	}
+	else if (!G[u].empty()) {
+		int tmp = 0;
+		for (auto& v : G[u]) v = dfs(v.f, u);
+	}
+	return ii(u, 1);
+}
+
+int solve(int u, int k) {
+	unordered_multiset<int> S;
+	for (auto& v : G[u]) {
+		int x = solve(v.f, k) + v.s;
+		if (x < 0) return -1e9;
+		if (x % k) S.insert(x % k);
+	}
+	int ret = 0;
+	while (!S.empty()) {
+		int x = *begin(S);
+		S.erase(S.find(x));
+		auto it = S.find(k - x);
+		if (it == end(S)) {
+			if (ret) return -1e9;
+			ret = x;
+		}
+		else S.erase(it);
+	}
+	return ret;
+}
+
+int main() {
+	ifstream cin("deleg.in");
+	ofstream cout("deleg.out");
+	ios_base::sync_with_stdio(0);
+	cin.tie(0), cout.tie(0);
+
+	int N; cin >> N;
+	for (int i = 1; i < N; ++i) {
+		int a, b; cin >> a >> b;
+		G[a].emplace_back(b, 1), G[b].emplace_back(a, 1);
+	}
+	int s = 1;
+	for (int u = 1; u <= N; ++u) {
+		if (G[u].size() > G[s].size()) s = u;
+	}
+	dfs(s, 0);
+	for (int i = 1; i < N; ++i) cout << ((N - 1) % i == 0 ? solve(s, i) == 0 : 0);
+}
diff --git a/19.5/feb/gold/timeline.cpp b/19.5/feb/gold/timeline.cpp
new file mode 100644
index 0000000..6a9c217
--- /dev/null
+++ b/19.5/feb/gold/timeline.cpp
@@ -0,0 +1,37 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+
+int S[100001];
+vector<ii> G[100001];
+
+int main() {
+	ifstream cin("timeline.in");
+	ofstream cout("timeline.out");
+
+	int N, M, C;
+	cin >> N >> M >> C;
+	for (int i = 0; i < N; ++i) cin >> S[i];
+	for (int i = 0; i < C; ++i) {
+		int a, b, x;
+		cin >> a >> b >> x;
+		G[--a].emplace_back(--b, -x);
+	}
+	for (int i = 0; i < N; ++i) S[i] = -S[i];
+	priority_queue<ii, vector<ii>, greater<ii>> pq;
+	for (int i = 0; i < N; ++i) pq.emplace(S[i], i);
+	while (!pq.empty()) {
+		int d = pq.top().f, u = pq.top().s;
+		pq.pop();
+		if (d > S[u]) continue;
+		for (auto& v : G[u]) {
+			if (S[u] + v.s < S[v.f]) {
+				S[v.f] = S[u] + v.s;
+				pq.emplace(S[v.f], v.f);
+			}
+		}
+	}
+	for (int i = 0; i < N; ++i) cout << -S[i] << '\n';
+}
diff --git a/19.5/feb/plat/help.cpp b/19.5/feb/plat/help.cpp
new file mode 100644
index 0000000..e6ae965
--- /dev/null
+++ b/19.5/feb/plat/help.cpp
@@ -0,0 +1,116 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/tree_policy.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/rope>
+#define init_io(s) ifstream cin((string)s+".in"); ofstream cout((string)s+".out"); ios_base::sync_with_stdio(false), cin.tie(NULL), cout.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 eb emplace_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;
+using namespace __gnu_pbds;
+using namespace __gnu_cxx;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef complex<ld> cd;
+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;
+typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
+typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; // WARNING: May be broken
+constexpr int INF = 1e9;
+constexpr ll LINF = 1e18;
+constexpr ll MOD = 1e9+7;
+const ld PI = 4*atan((ld)1);
+
+inline int imod(int i) { return i > MOD ? i - MOD : i; }
+
+int N, pow2[100005] = { 1 };
+ii S[100005];
+struct seg_tree {
+	int seg[800005] = { 0 }, tmp[800005] = { 0 };
+	void pull(int n) { seg[n] = imod(seg[n<<1]+seg[n<<1|1]); }
+	void push(int l, int r, int n) {
+		seg[n] = ((ll)pow2[tmp[n]]*seg[n])%MOD;
+		if (l != r) tmp[n<<1] += tmp[n], tmp[n<<1|1] += tmp[n];
+		tmp[n] = 0;
+	}
+	void update(int x, int v, int l = 1, int r = -1, int n = 1) {
+		if (r == -1) r = 2*N;
+		if (tmp[n]) push(l, r, n);
+		if (l == r) seg[n] = imod(v+seg[n]);
+		else {
+			int m = (l + r) >> 1;
+			x <= m ? update(x, v, l, m, n<<1) : update(x, v, m + 1, r, n<<1|1);
+			pull(n);
+		}
+	}
+	void update_range(int a, int b, int l = 1, int r = -1, int n = 1) {
+		if (r == -1) r = 2*N;
+		if (tmp[n]) push(l, r, n);
+		if (l > b || r < a) return;
+		if (l >= a && r <= b) {
+			tmp[n]++;
+			push(l, r, n);
+		}
+		else {
+			int m = (l + r) >> 1;
+			update_range(a, b, l, m, n<<1), update_range(a, b, m + 1, r, n<<1|1);
+			pull(n);
+		}
+	}
+	int query(int a, int b, int l = 1, int r = -1, int n = 1) {
+		if (r == -1) r = 2*N;
+		if (a > b || l > b || r < a) return 0;
+		if (tmp[n]) push(l, r, n);
+		if (l >= a && r <= b) return seg[n];
+		int m = (l + r) >> 1;
+		return imod(query(a, b, l, m, n<<1) + query(a, b, m + 1, r, n<<1|1));
+	}
+} dp[11];
+
+int main() {
+	init_io("help");
+
+	int fact[11] = { 1 }, nCr[11][11];
+	for (int i = 0; i < 10; i++) fact[i+1] = (i+1)*fact[i];
+	for (int i = 0; i <= 10; i++) {
+		for (int j = 0; j <= i; j++) nCr[i][j] = fact[i]/fact[j]/fact[i-j];
+	}
+	for (int i = 0; i < 100000; i++) pow2[i+1] = imod(pow2[i]<<1);
+
+	int K;
+	cin >> N >> K;
+	for (int i = 0; i < N; ++i) cin >> S[i].f >> S[i].s;
+	sort(S, S + N);
+
+	for (int i = 0; i < N; ++i) {
+		int tmp[11];
+		for (int j = 0; j <= K; ++j) {
+			tmp[j] = dp[j].query(1, S[i].f);
+			ll sum = dp[j].query(S[i].f, S[i].s-1);
+			for (int k = 0; k <= j; ++k) {
+				sum += (ll)nCr[j][k]*tmp[k];
+			}
+			dp[j].update(S[i].s, sum%MOD+1);
+		}
+		for (int j = 0; j <= K; ++j) {
+			dp[j].update_range(S[i].s+1, 2*N);
+		}
+	}
+
+	cout << dp[K].query(1, 2*N) << endl;
+}
diff --git a/19.5/jan/gold/boards.cpp b/19.5/jan/gold/boards.cpp
new file mode 100644
index 0000000..812c959
--- /dev/null
+++ b/19.5/jan/gold/boards.cpp
@@ -0,0 +1,50 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef pair<int, int> ii;
+constexpr int INF = 1e9;
+
+struct node {
+	int val; node* c[2];
+	node() { val = -INF; c[0] = c[1] = 0; }
+	node* get_c(int i) { return (!c[i] ? c[i] = new node : c[i]); }
+	void update(int x, int v, int l = 0, int r = INF) {
+		if (l == r) val = max(v, val);
+		else {
+			int m = (l + r) >> 1;
+			x <= m ? get_c(0)->update(x, v, l, m) : get_c(1)->update(x, v, m + 1, r);
+			val = max(c[0] ? c[0]->val : -INF, c[1] ? c[1]->val : -INF);
+		}
+	}
+	int query(int a, int b, int l = 0, int r = INF) {
+		if (a > r || b < l) return -INF;
+		if (a <= l && b >= r) return val;
+		int m = (l + r) >> 1;
+		return max(c[0] ? c[0]->query(a, b, l, m) : -INF, c[1] ? c[1]->query(a, b, m + 1, r) : -INF);
+	}
+} seg;
+
+pair<ii, ii> A[100001];
+
+int main() {
+	ifstream cin("boards.in");
+	ofstream cout("boards.out");
+
+	int N, P;
+	cin >> N >> P;
+	for (int i = 0; i < P; ++i) cin >> A[i].f.f >> A[i].f.s >> A[i].s.f >> A[i].s.s;
+	sort(A, A + P);
+	
+	seg.update(0, 0);
+	set<pair<ii, int>> S;
+	for (int i = 0; i < P; ++i) {
+		S.emplace(A[i].s, A[i].f.f + A[i].f.s - seg.query(0, A[i].f.s));
+		auto it = S.begin();
+		while (it != S.end() && it->f.f <= (i < P - 1 ? A[i + 1].f.f : INF)) {
+			seg.update(it->f.s, it->f.f + it->f.s - it->s);
+			it = S.erase(it);
+		}		
+	}
+	cout << 2 * N - seg.query(0, N);
+}
diff --git a/19.5/jan/gold/threesum.cpp b/19.5/jan/gold/threesum.cpp
new file mode 100644
index 0000000..21e266c
--- /dev/null
+++ b/19.5/jan/gold/threesum.cpp
@@ -0,0 +1,40 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+typedef long long ll;
+typedef pair<int, int> ii;
+constexpr int MAX = 1e6;
+
+int A[5005], cnt[5005] = { 0 }, M[2000002];
+ll ans[100001] = { 0 };
+vector<pair<ii, int>> q;
+
+int main() {
+	ifstream cin("threesum.in");
+	ofstream cout("threesum.out");
+
+	int N, Q; cin >> N >> Q;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+	for (int i = 0; i < Q; ++i) {
+		int a, b; cin >> a >> b;
+		if (a != b) q.emplace_back(ii(--a, --b), i);
+	}
+	sort(begin(q), end(q), [](const pair<ii, int>& a, const pair<ii, int>& b) {
+		return a.f.s < b.f.s || (a.f.s == b.f.s && a.f.f > b.f.f);
+	});
+	
+	auto it = begin(q);
+	for (int i = 0; i < N; ++i) {
+		ll sum = 0;
+		for (int j = i - 1; j >= 0; --j) {
+			int tmp = A[i] + A[j] + MAX;
+			if (tmp > 0 && tmp <= 2 * MAX && M[tmp]) cnt[j] += M[tmp];
+			++M[-A[j] + MAX];
+			sum += cnt[j];
+			while (it != end(q) && ii(j, i) == it->f) ans[(it++)->s] = sum;
+		}
+		for (int j = i - 1; j >= 0; --j) --M[-A[j] + MAX];
+	}
+	for (int i = 0; i < Q; ++i) cout << ans[i] << '\n';
+}
diff --git a/19.5/jan/gold/time.cpp b/19.5/jan/gold/time.cpp
new file mode 100644
index 0000000..fd3b8cf
--- /dev/null
+++ b/19.5/jan/gold/time.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int m[1001], DP[1001][1001];
+vector<int> G[1001];
+
+int main() {
+	ifstream cin("time.in");
+	ofstream cout("time.out");
+
+	int N, M, C;
+	cin >> N >> M >> C;
+	for (int u = 1; u <= N; ++u) cin >> m[u];
+	while (M--) {
+		int a, b;
+		cin >> a >> b;
+		G[a].push_back(b);
+	}
+
+	memset(DP, -1, sizeof DP);
+	DP[0][1] = 0;
+	for (int i = 0; i < 1000; ++i) {
+		for (int u = 1; u <= N; ++u) {
+			if (DP[i][u] != -1) {
+				for (auto& v : G[u]) {
+					DP[i + 1][v] = max(DP[i][u] + m[v], DP[i + 1][v]);
+				}
+			}
+		}
+	}
+
+	int ans = 0;
+	for (int i = 1; i <= 1000; ++i) ans = max(DP[i][1] - C * i * i, ans);
+	cout << ans << '\n';
+}
diff --git a/19.5/jan/plat/nondec.cpp b/19.5/jan/plat/nondec.cpp
new file mode 100644
index 0000000..2084a05
--- /dev/null
+++ b/19.5/jan/plat/nondec.cpp
@@ -0,0 +1,108 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/tree_policy.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/rope>
+#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 eb emplace_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;
+using namespace __gnu_pbds;
+using namespace __gnu_cxx;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef complex<ld> cd;
+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;
+typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
+typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; // WARNING: May be broken
+constexpr int INF = 1e9;
+constexpr ll LINF = 1e18;
+const ll MOD = 1e9+7;
+const ll INV = 5e8+4;
+const int S = 200;
+const ld PI = 4*atan((ld)1);
+void io(str s) {
+    if (fopen((s+".in").c_str(), "r")) {
+        freopen((s+".in").c_str(), "r", stdin);
+        freopen((s+".out").c_str(), "w", stdout);
+    } 
+    ios_base::sync_with_stdio(false);
+    cin.tie(NULL), cout.tie(NULL);
+}
+
+
+int N, K, A[50001], cl[50001][21], cr[50001][21], ans[200001];
+
+void solve(int l, int r, vector<pair<ii, int>>& q) {
+    int m = (l + r) >> 1;
+    for (int i = l; i <= r; i++) memset(cl[i], 0, sizeof(cl[i])), memset(cr[i], 0, sizeof(cr[i]));
+    int c[21][21] = { 0 };
+    for (int i = m; i >= l; i--) {
+        if (i < m) memcpy(cl[i], cl[i + 1], sizeof(cl[i]));
+        for (int j = A[i]; j <= K; j++) {
+            for (int k = A[i]; k <= K; k++) {
+                cl[i][j] = (c[k][j] + cl[i][j]) % MOD;
+                c[A[i]][j] = (c[k][j] + c[A[i]][j]) % MOD;
+            }
+        }
+        cl[i][A[i]]++, c[A[i]][A[i]]++;
+    }
+    memset(c, 0, sizeof(c));
+    for (int i = m + 1; i <= r; i++) {
+        if (i > m + 1) memcpy(cr[i], cr[i - 1], sizeof(cr[i]));
+        for (int j = A[i]; j > 0; j--) {
+            for (int k = A[i]; k > 0; k--) {
+                cr[i][j] = (c[j][k] + cr[i][j]) % MOD;
+                c[j][A[i]] = (c[j][k] + c[j][A[i]]) % MOD;
+            }
+        }
+        cr[i][A[i]]++, c[A[i]][A[i]]++;
+    }
+    vector<pair<ii, int>> ql, qr;
+    for (auto& x : q) {
+        if (x.f.f <= m && x.f.s > m) {
+            ll cnt = 0;
+            for (int i = 1; i <= K; i++) {
+                cnt = (cl[x.f.f][i] + cnt) % MOD;
+                ans[x.s] = (cnt * cr[x.f.s][i] + cl[x.f.f][i] + cr[x.f.s][i] + ans[x.s]) % MOD;
+            }
+        }
+        else if (x.f.s <= m) ql.pb(x);
+        else qr.pb(x);
+    }
+    if (l == r) return;
+    solve(l, m, ql), solve(m + 1, r, qr);
+}
+
+int main() {
+    io("nondec");
+
+    cin >> N >> K;
+    for (int i = 0; i < N; i++) cin >> A[i];
+
+    int Q;
+    cin >> Q;
+    vector<pair<ii, int>> q(Q);
+    for (int i = 0; i < Q; i++) {
+        cin >> q[i].f.f >> q[i].f.s;
+        q[i].f.f--, q[i].f.s--;
+        q[i].s = i;
+    }
+    solve(0, N - 1, q);
+    for (int i = 0; i < Q; i++) cout << ans[i] + (q[i].f.f == q[i].f.s) + 1 << '\n';    
+}
diff --git a/19.5/open/gold/exercise.cpp b/19.5/open/gold/exercise.cpp
new file mode 100644
index 0000000..7e8ba80
--- /dev/null
+++ b/19.5/open/gold/exercise.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+int sieve_size;
+bitset<10000001> bs;
+vector<int> pr;
+
+void sieve(int size) {
+	sieve_size = size;
+	bs.set(); bs[0] = bs[1] = 0;
+  	for (ll i = 2; i <= sieve_size; ++i) if (bs[i]) {
+		for (ll j = i * i; j <= sieve_size; j += i) bs[j] = 0;
+		pr.push_back(i);
+	}
+}
+
+int DP[10001] = { 1 };
+
+int main() {
+	ifstream cin("exercise.in");
+	ofstream cout("exercise.out");
+
+	int N, M;
+	cin >> N >> M;
+	sieve(N);
+	for (auto& p : pr) {
+		for (int i = N; i >= 0; --i) {
+			for (int j = p; j <= N - i; j *= p) DP[i + j] = ((ll)j * DP[i] + DP[i + j]) % M;
+		}
+	}
+	int ans = 0;
+	for (int i = 0; i <= N; ++i) ans = (DP[i] + ans) % M;
+	cout << ans << '\n';
+}
diff --git a/19.5/open/gold/fcolor.cpp b/19.5/open/gold/fcolor.cpp
new file mode 100644
index 0000000..5a3879d
--- /dev/null
+++ b/19.5/open/gold/fcolor.cpp
@@ -0,0 +1,38 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int cnt = 0, c[200002], p[200002], ans[200002];
+bitset<200002> vis;
+vector<int> G[200002], H[200002];
+
+void dfs(int u) {
+	vis[u] = 1;
+	for (auto& v : G[u]) {
+		if (!vis[v]) dfs(v);
+		if (c[v]) c[u] = max(p[c[v]], c[u]);
+	}
+	for (auto& v : H[u]) {
+		if (!vis[v]) dfs(v);
+		if (c[u]) c[v] = max(p[c[u]], c[v]);
+	}
+	if (!c[u]) c[u] = ++cnt;
+	for (auto& v : G[u]) if (c[v]) p[c[v]] = max(c[u], p[c[v]]);
+	for (auto& v : H[u]) if (c[v]) p[c[u]] = max(c[v], p[c[u]]);
+}
+
+int main() {
+	ifstream cin("fcolor.in");
+	ofstream cout("fcolor.out");
+
+	int N, M; cin >> N >> M;
+	while (M--) {
+		int a, b; cin >> a >> b;
+		G[b].push_back(a), H[a].push_back(b);
+	}
+	for (int u = 1; u <= N; ++u) dfs(u);
+	vis.reset();
+	for (int u = 1; u <= N; ++u) dfs(u);
+	cnt = 0;
+	for (int u = 1; u <= N; ++u) if (!ans[c[u]]) ans[c[u]] = ++cnt;
+	for (int u = 1; u <= N; ++u) cout << ans[c[u]] << '\n';
+}
diff --git a/19.5/open/gold/haircut.cpp b/19.5/open/gold/haircut.cpp
new file mode 100644
index 0000000..0e93c45
--- /dev/null
+++ b/19.5/open/gold/haircut.cpp
@@ -0,0 +1,59 @@
+#include <bits/stdc++.h>
+using namespace std;
+typedef long long ll;
+
+template<typename T> class fenwick_tree {
+private: vector<T> FT;
+public:
+	fenwick_tree(int N) { FT.assign(N + 1, 0); }
+	void update(int x, T val) { if (x > 0) for (; x < FT.size(); x += x & -x) FT[x] += val; }
+	T query(int x) { T ret = 0; if (x > 0) for (; x > 0; x -= x & -x) ret += FT[x]; return ret; }
+	T query(int x, int y) { return query(y) - query(x - 1); }
+};
+
+ll N, seg[400004] = { 0 }, tmp[400004] = { 0 };
+inline ll pull(const ll& l, const ll& r) { return l + r; }
+inline void push(int l, int r, int n) {
+	seg[n] += (r - l + 1) * tmp[n];
+	if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n];
+	tmp[n] = 0;
+}
+void update(int a, int b, ll v, int l = 0, int r = -1, int n = 1) {
+	if (r == -1) r = N - 1;
+	push(l, r, n);
+	if (l > b || r < a) return;
+	if (l >= a && r <= b) {
+		tmp[n] += v;
+		push(l, r, n);
+	}
+	else {
+		int m = (l + r) >> 1;
+		update(a, b, v, l, m, n << 1), update(a, b, v, m + 1, r, n << 1 | 1);
+		seg[n] = pull(seg[n << 1], seg[n << 1 | 1]);
+	}
+}
+ll query(int a, int b, int l = 0, int r = -1, int n = 1) {
+	if (r == -1) r = N - 1;
+	if (a > b || l > b || r < a) return 0;
+	push(l, r, n);
+	if (l >= a && r <= b) return seg[n];
+	int m = (l + r) >> 1;
+	return pull(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1));
+}
+
+int A[100001];
+
+int main() {
+	ifstream cin("haircut.in");
+	ofstream cout("haircut.out");
+
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+
+	fenwick_tree<ll> FT(N);
+	for (int i = 0; i < N; ++i) {
+		update(A[i] + 1, N, FT.query(A[i] + 1, N));
+		FT.update(A[i], 1);
+	}
+	for (int i = 0; i < N; ++i) cout << query(i, i) << '\n';
+}
diff --git a/19.5/open/plat/sprinklers2.cpp b/19.5/open/plat/sprinklers2.cpp
new file mode 100644
index 0000000..fd2fe5a
--- /dev/null
+++ b/19.5/open/plat/sprinklers2.cpp
@@ -0,0 +1,68 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/tree_policy.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/rope>
+#define init_io(s) ifstream cin((string)s+".in"); ofstream cout((string)s+".out"); ios_base::sync_with_stdio(false), cin.tie(NULL), cout.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 eb emplace_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;
+using namespace __gnu_pbds;
+using namespace __gnu_cxx;
+typedef string str;
+typedef long long ll;
+typedef long double ld;
+typedef complex<ld> cd;
+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;
+typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
+typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; // WARNING: May be broken
+constexpr int INF = 1e9;
+constexpr ll LINF = 1e18;
+constexpr ll MOD = 1e9+7;
+const ld PI = 4*atan((ld)1);
+
+char G[2002][2002];
+ll pow2[2002] = { 1 }, DP[2002][2002][2] = { 0 };
+
+int main() {
+	init_io("sprinklers2");
+
+	int N;
+	cin >> N;
+	for (int i = 0; i < N; ++i) {
+		for (int j = 0; j < N; ++j) cin >> G[i][j];
+	}
+
+	for (int i = 0; i < N; ++i) pow2[i + 1] = (pow2[i] << 1) % MOD;
+	
+	DP[0][0][1] = 1;
+	for (int i = 0; i < N; ++i) {
+		ll l = 0, r = 0, sum = 0;
+		for (int j = 1; j < N; ++j) r += G[i][j] == '.';
+		for (int j = 0; j <= N; ++j) {
+            if (j && j < N) r -= G[i][j] == '.';
+            DP[i + 1][j][j == N] = (pow2[l] * pow2[r] % MOD) * (((j && G[i][j - 1] == '.') + 1) * (DP[i][j][0] + DP[i][j][1]) + (j && G[i][j - 1] == '.') * sum) % MOD;
+            if (j < N && G[i][j] == '.') DP[i + 1][j][1] = DP[i + 1][j][0];
+            if (j < N) sum = (DP[i][j][1] + sum) % MOD;
+            if (j) l += G[i][j - 1] == '.';
+		}
+	}
+	ll ans = 0;
+	for (int i = 0; i <= N; ++i) ans = (DP[N][i][1] + ans) % MOD;
+	cout << ans << '\n';
+}