aboutsummaryrefslogtreecommitdiff
path: root/19.5
diff options
context:
space:
mode:
Diffstat (limited to '19.5')
-rw-r--r--19.5/dec/gold/cowmbat.cpp48
-rw-r--r--19.5/dec/gold/milkvisits.cpp70
-rw-r--r--19.5/dec/gold/pump.cpp46
-rw-r--r--19.5/dec/plat/snowcow.cpp127
-rw-r--r--19.5/feb/gold/deleg.cpp66
-rw-r--r--19.5/feb/gold/timeline.cpp37
-rw-r--r--19.5/feb/plat/help.cpp116
-rw-r--r--19.5/jan/gold/boards.cpp50
-rw-r--r--19.5/jan/gold/threesum.cpp40
-rw-r--r--19.5/jan/gold/time.cpp35
-rw-r--r--19.5/jan/plat/nondec.cpp108
-rw-r--r--19.5/open/gold/exercise.cpp35
-rw-r--r--19.5/open/gold/fcolor.cpp38
-rw-r--r--19.5/open/gold/haircut.cpp59
-rw-r--r--19.5/open/plat/sprinklers2.cpp68
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';
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2024-12-23 03:30:11 +0000