From 4650ca79be4666885a83954d7d95d5b6c80202ce Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 6 Oct 2020 17:25:19 -0500 Subject: Restructured directories --- 07/nov/gold/telewire.cpp | 15 +++ 11/dec/gold/photo.cpp | 22 +++++ 12/mar/gold/restack.cpp | 16 +++ 12/nov/gold/bbreeds.cpp | 14 +++ 12/nov/gold/btree.cpp | 80 +++++++++++++++ 13/feb/gold/route.cpp | 29 ++++++ 13/nov/gold/nochange.cpp | 37 +++++++ 13/open/gold/yinyang.cpp | 97 +++++++++++++++++++ 14/dec/gold/guard.cpp | 17 ++++ 15/dec/plat/maxflow.cpp | 59 +++++++++++ 15/open/gold/googol.py | 12 +++ 16/dec/plat/triangles.cpp | 113 ++++++++++++++++++++++ 16/open/plat/landscape.cpp | 70 ++++++++++++++ 17/feb/plat/friendcross.cpp | 68 +++++++++++++ 17/feb/plat/mincross.cpp | 57 +++++++++++ 17/feb/plat/nocross.cpp | 57 +++++++++++ 17/open/plat/cowbasic.cpp | 103 ++++++++++++++++++++ 18/dec/plat/balance.cpp | 62 ++++++++++++ 18/dec/plat/itout.cpp | 99 +++++++++++++++++++ 18/feb/plat/gymnasts.cpp | 97 +++++++++++++++++++ 18/feb/plat/newbarn.cpp | 78 +++++++++++++++ 18/feb/plat/newbarn_naive.cpp | 72 ++++++++++++++ 18/open/plat/sort.cpp | 161 +++++++++++++++++++++++++++++++ 19/dec/gold/cowmbat.cpp | 48 +++++++++ 19/dec/gold/milkvisits.cpp | 70 ++++++++++++++ 19/dec/gold/pump.cpp | 46 +++++++++ 19/dec/plat/snowcow.cpp | 127 ++++++++++++++++++++++++ 19/open/plat/boxes.cpp | 75 ++++++++++++++ 20/feb/gold/deleg.cpp | 66 +++++++++++++ 20/feb/gold/timeline.cpp | 37 +++++++ 20/feb/plat/help.cpp | 116 ++++++++++++++++++++++ 20/jan/gold/boards.cpp | 50 ++++++++++ 20/jan/gold/threesum.cpp | 40 ++++++++ 20/jan/gold/time.cpp | 35 +++++++ 20/jan/plat/nondec.cpp | 108 +++++++++++++++++++++ 20/open/gold/exercise.cpp | 35 +++++++ 20/open/gold/fcolor.cpp | 38 ++++++++ 20/open/gold/haircut.cpp | 59 +++++++++++ 20/open/plat/sprinklers2.cpp | 68 +++++++++++++ 2007/November/Gold/telewire.cpp | 15 --- 2011/December/Gold/photo.cpp | 22 ----- 2012/March/Gold/restack.cpp | 16 --- 2012/November/Gold/bbreeds.cpp | 14 --- 2012/November/Gold/btree.cpp | 80 --------------- 2013/February/Gold/route.cpp | 29 ------ 2013/November/Gold/nochange.cpp | 37 ------- 2013/US Open/Gold/yinyang.cpp | 97 ------------------- 2014/December/Gold/guard.cpp | 17 ---- 2015/December/Platinum/maxflow.cpp | 59 ----------- 2015/US Open/Gold/googol.py | 12 --- 2016/December/Platinum/triangles.cpp | 113 ---------------------- 2016/US Open/Platinum/landscape.cpp | 70 -------------- 2017/February/Platinum/friendcross.cpp | 68 ------------- 2017/February/Platinum/mincross.cpp | 57 ----------- 2017/February/Platinum/nocross.cpp | 57 ----------- 2017/US Open/Platinum/cowbasic.cpp | 103 -------------------- 2018/December/Platinum/balance.cpp | 62 ------------ 2018/December/Platinum/itout.cpp | 99 ------------------- 2018/February/Platinum/gymnasts.cpp | 97 ------------------- 2018/February/Platinum/newbarn.cpp | 78 --------------- 2018/February/Platinum/newbarn_naive.cpp | 72 -------------- 2018/US Open/Platinum/sort.cpp | 161 ------------------------------- 2019/December/Gold/cowmbat.cpp | 48 --------- 2019/December/Gold/milkvisits.cpp | 70 -------------- 2019/December/Gold/pump.cpp | 46 --------- 2019/December/Platinum/snowcow.cpp | 127 ------------------------ 2019/US Open/Platinum/boxes.cpp | 75 -------------- 2020/February/Gold/deleg.cpp | 66 ------------- 2020/February/Gold/timeline.cpp | 37 ------- 2020/February/Platinum/help.cpp | 116 ---------------------- 2020/January/Gold/boards.cpp | 50 ---------- 2020/January/Gold/threesum.cpp | 40 -------- 2020/January/Gold/time.cpp | 35 ------- 2020/January/Platinum/nondec.cpp | 108 --------------------- 2020/US Open/Gold/exercise.cpp | 35 ------- 2020/US Open/Gold/fcolor.cpp | 38 -------- 2020/US Open/Gold/haircut.cpp | 59 ----------- 2020/US Open/Platinum/sprinklers2.cpp | 68 ------------- 78 files changed, 2453 insertions(+), 2453 deletions(-) create mode 100644 07/nov/gold/telewire.cpp create mode 100644 11/dec/gold/photo.cpp create mode 100644 12/mar/gold/restack.cpp create mode 100644 12/nov/gold/bbreeds.cpp create mode 100644 12/nov/gold/btree.cpp create mode 100644 13/feb/gold/route.cpp create mode 100644 13/nov/gold/nochange.cpp create mode 100644 13/open/gold/yinyang.cpp create mode 100644 14/dec/gold/guard.cpp create mode 100644 15/dec/plat/maxflow.cpp create mode 100644 15/open/gold/googol.py create mode 100644 16/dec/plat/triangles.cpp create mode 100644 16/open/plat/landscape.cpp create mode 100644 17/feb/plat/friendcross.cpp create mode 100644 17/feb/plat/mincross.cpp create mode 100644 17/feb/plat/nocross.cpp create mode 100644 17/open/plat/cowbasic.cpp create mode 100644 18/dec/plat/balance.cpp create mode 100644 18/dec/plat/itout.cpp create mode 100644 18/feb/plat/gymnasts.cpp create mode 100644 18/feb/plat/newbarn.cpp create mode 100644 18/feb/plat/newbarn_naive.cpp create mode 100644 18/open/plat/sort.cpp create mode 100644 19/dec/gold/cowmbat.cpp create mode 100644 19/dec/gold/milkvisits.cpp create mode 100644 19/dec/gold/pump.cpp create mode 100644 19/dec/plat/snowcow.cpp create mode 100644 19/open/plat/boxes.cpp create mode 100644 20/feb/gold/deleg.cpp create mode 100644 20/feb/gold/timeline.cpp create mode 100644 20/feb/plat/help.cpp create mode 100644 20/jan/gold/boards.cpp create mode 100644 20/jan/gold/threesum.cpp create mode 100644 20/jan/gold/time.cpp create mode 100644 20/jan/plat/nondec.cpp create mode 100644 20/open/gold/exercise.cpp create mode 100644 20/open/gold/fcolor.cpp create mode 100644 20/open/gold/haircut.cpp create mode 100644 20/open/plat/sprinklers2.cpp delete mode 100644 2007/November/Gold/telewire.cpp delete mode 100644 2011/December/Gold/photo.cpp delete mode 100644 2012/March/Gold/restack.cpp delete mode 100644 2012/November/Gold/bbreeds.cpp delete mode 100644 2012/November/Gold/btree.cpp delete mode 100644 2013/February/Gold/route.cpp delete mode 100644 2013/November/Gold/nochange.cpp delete mode 100644 2013/US Open/Gold/yinyang.cpp delete mode 100644 2014/December/Gold/guard.cpp delete mode 100644 2015/December/Platinum/maxflow.cpp delete mode 100644 2015/US Open/Gold/googol.py delete mode 100644 2016/December/Platinum/triangles.cpp delete mode 100644 2016/US Open/Platinum/landscape.cpp delete mode 100644 2017/February/Platinum/friendcross.cpp delete mode 100644 2017/February/Platinum/mincross.cpp delete mode 100644 2017/February/Platinum/nocross.cpp delete mode 100644 2017/US Open/Platinum/cowbasic.cpp delete mode 100644 2018/December/Platinum/balance.cpp delete mode 100644 2018/December/Platinum/itout.cpp delete mode 100644 2018/February/Platinum/gymnasts.cpp delete mode 100644 2018/February/Platinum/newbarn.cpp delete mode 100644 2018/February/Platinum/newbarn_naive.cpp delete mode 100644 2018/US Open/Platinum/sort.cpp delete mode 100644 2019/December/Gold/cowmbat.cpp delete mode 100644 2019/December/Gold/milkvisits.cpp delete mode 100644 2019/December/Gold/pump.cpp delete mode 100644 2019/December/Platinum/snowcow.cpp delete mode 100644 2019/US Open/Platinum/boxes.cpp delete mode 100644 2020/February/Gold/deleg.cpp delete mode 100644 2020/February/Gold/timeline.cpp delete mode 100644 2020/February/Platinum/help.cpp delete mode 100644 2020/January/Gold/boards.cpp delete mode 100644 2020/January/Gold/threesum.cpp delete mode 100644 2020/January/Gold/time.cpp delete mode 100644 2020/January/Platinum/nondec.cpp delete mode 100644 2020/US Open/Gold/exercise.cpp delete mode 100644 2020/US Open/Gold/fcolor.cpp delete mode 100644 2020/US Open/Gold/haircut.cpp delete mode 100644 2020/US Open/Platinum/sprinklers2.cpp diff --git a/07/nov/gold/telewire.cpp b/07/nov/gold/telewire.cpp new file mode 100644 index 0000000..e68ae69 --- /dev/null +++ b/07/nov/gold/telewire.cpp @@ -0,0 +1,15 @@ +#include +#include +using namespace std; +constexpr auto INF = (int)1e9; + +int main() { + int N, C, H, A[105], B[105], DP[105]; + cin >> N >> C; + for (int i = 0; i < N; i++) { cin >> H; + for (int j = 0; j <= 100; j++) DP[j] = (j < H ? INF : (j - H) * (j - H) + (i > 0) * min(A[j] + C * j, B[j] - C * j)); + for (int j = 0; j <= 100; j++) A[j] = min(DP[j] - C * j, (j <= 0 ? INF : A[j - 1])); + for (int j = 100; j >= 0; j--) B[j] = min(DP[j] + C * j, (j >= 100 ? INF : B[j + 1])); + } + cout << *min_element(DP, DP + 100) << endl; +} diff --git a/11/dec/gold/photo.cpp b/11/dec/gold/photo.cpp new file mode 100644 index 0000000..3492b8c --- /dev/null +++ b/11/dec/gold/photo.cpp @@ -0,0 +1,22 @@ +#include +using namespace std; + +int A[5][20005]; + +int main { + int N; + cin >> N; + for (int i = 0; i < 5; i++) { + for (int j = 0; j < N; j++) cin >> A[i][j]; + } + unordered_map m[5]; + for (int i = 0; i < 5; i++) { + for (int j = 0; j < N; j++) m[i][A[i][j]] = j; + } + sort(A[0], A[0] + N, [&m](const int& a, const int& b) { + int c[2] = { 0 }; + for (int i = 0; i < 5; i++) c[m[i][a] < m[i][b]]++; + return c[0] < c[1]; + }); + for (int i = 0; i < N; i++) cout << A[0][i] << '\n'; +} diff --git a/12/mar/gold/restack.cpp b/12/mar/gold/restack.cpp new file mode 100644 index 0000000..49b325d --- /dev/null +++ b/12/mar/gold/restack.cpp @@ -0,0 +1,16 @@ +#include +using namespace std; + +int main() { + ifstream cin("restack.in"); + ofstream cout("restack.out"); + int n, c = 0, ans = 0; cin >> n; + vector v; + for (int i = 0; i < n; i++) { + int a, b; cin >> a >> b; + v.push_back(c += a - b); + } + sort(v.begin(), v.end()); + for (int i = 0; i < n; i++) ans += abs(v[i] - v[n / 2]); + cout << ans << '\n'; +} diff --git a/12/nov/gold/bbreeds.cpp b/12/nov/gold/bbreeds.cpp new file mode 100644 index 0000000..9d7a745 --- /dev/null +++ b/12/nov/gold/bbreeds.cpp @@ -0,0 +1,14 @@ +#include +#include +using namespace std; + +int main() { + string S; cin >> S; + int x = 0, DP[1005] = { 1 }; + for (auto c : S) { + if (c == '(') for (x++, int i = x; i > 0; i--) DP[i] = (DP[i - 1] + DP[i]) % 2012; + else for (x--, int i = 0; i <= x; i++) DP[i] = (DP[i] + DP[i + 1]) % 2012; + DP[x + 1] = 0; + } + cout << DP[0] << endl; +} diff --git a/12/nov/gold/btree.cpp b/12/nov/gold/btree.cpp new file mode 100644 index 0000000..16462ab --- /dev/null +++ b/12/nov/gold/btree.cpp @@ -0,0 +1,80 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +int L[40005]; +vi G[40005]; +map A[40005]; +map> B[40005]; + +int dfs(int u, int d) { + int ret = 0; + L[u] == 1 ? A[u][d] = 1 : B[u][d] = 1; + for (auto& v : G[u]) { + ret = max(dfs(v, L[v] + d), ret); + for (auto& x : A[v]) { + if (B[u].find(2 * d - L[u] - x.first) != B[u].end()) { // Match left side with corresponding right side + ret = max(max(x.second, B[u][2 * d - L[u] - x.first]), ret); + } + } + for (auto& x : B[v]) { + if (A[u].find(2 * d - L[u] - x.first) != A[u].end()) { // Match right side with corresponding left side + ret = max(max(x.second, A[u][2 * d - L[u] - x.first]), ret); + } + } + for (auto& x : A[v]) A[u][x.first] = max(max(x.first - d, x.second), A[u][x.first]); // Merge A[v] to A[u], adjust max nesting depth accordingly + for (auto& x : B[v]) B[u][x.first] = max(max(d - x.first, x.second), B[u][x.first]); // Merge B[v] to B[u], adjust max nesting depth accordingly + A[v].clear(), B[v].clear(); + } + while (!A[u].empty() && A[u].begin()->first < d) A[u].erase(A[u].begin()); + while (!B[u].empty() && B[u].begin()->first > d) B[u].erase(B[u].begin()); + return ret; +} + +int main() { + init_io("btree"); + int N; cin >> N; + for (int i = 1; i < N; i++) { + int p; cin >> p; + G[--p].push_back(i); + } + for (int i = 0; i < N; i++) { + char c; cin >> c; + L[i] = (c == '(' ? 1 : -1); + } + cout << dfs(0, L[0]); +} diff --git a/13/feb/gold/route.cpp b/13/feb/gold/route.cpp new file mode 100644 index 0000000..aab04ed --- /dev/null +++ b/13/feb/gold/route.cpp @@ -0,0 +1,29 @@ +#include +#include +using namespace std; +constexpr auto INF = (int)1e9; +typedef pair ii; + +int l[40005], r[40005], dl[40005] = { 0 }, dr[40005] = { 0 }; +ii E[100005]; + +int main() { + int N, M, R; + cin >> N >> M >> R; + for (int i = 0; i < N; i++) cin >> l[i]; + for (int i = 0; i < M; i++) cin >> r[i]; + for (int i = 0; i < R; i++) cin >> E[i].first >> E[i].second; + + sort(E, E + R, [](const ii& a, const ii& b) { return a.first + a.second < b.first + b.second; }); + + for (int i = 0; i < N; i++) dl[i] = l[i]; + for (int i = 0; i < M; i++) dr[i] = r[i]; + + for (int i = 0; i < R; i++) { + int u = E[i].first, v = E[i].second, a = dl[--u], b = dr[--v]; + dl[u] = max(l[u] + b, dl[u]); + dr[v] = max(r[v] + a, dr[v]); + } + + cout << max(*max_element(dl, dl + N), *max_element(dr, dr + N)) << endl; +} diff --git a/13/nov/gold/nochange.cpp b/13/nov/gold/nochange.cpp new file mode 100644 index 0000000..ad34b80 --- /dev/null +++ b/13/nov/gold/nochange.cpp @@ -0,0 +1,37 @@ +#include +#include +using namespace std; + +int v[20], p[100005] = { 0 }, DP[1 << 16]; + +inline int sum(int i, int j) { return p[j + 1] - p[i]; } + +int main() { + int K, N; cin >> K >> N; + for (int i = 0; i < K; i++) cin >> v[i]; + for (int i = 0; i < N; i++) { + int c; cin >> c; + p[i + 1] = c + p[i]; + } + + for (int i = 0; i < (1 << K); i++) if (DP[i] < N) { + for (int j = 0; j < K; j++) if ((i & 1 << j) == 0) { + int l = DP[i], h = N; + while (l + 1 < h) { + int m = (l + h) / 2; + sum(DP[i], m) > v[j] ? h = m : l = m; + } + DP[i ^ 1 << j] = max(l + 1, DP[i ^ 1 << j]); + } + } + + int ans = -1; + for (int i = 0; i < (1 << K); i++) { + if (DP[i] == N) { + int sum = 0; + for (int j = 0; j < K; j++) if ((i & 1 << j) == 0) sum += v[j]; + ans = max(sum, ans); + } + } + cout << ans << endl; +} diff --git a/13/open/gold/yinyang.cpp b/13/open/gold/yinyang.cpp new file mode 100644 index 0000000..9ce4aec --- /dev/null +++ b/13/open/gold/yinyang.cpp @@ -0,0 +1,97 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 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)) +#define uset unordered_set +#define umap unordered_map +using namespace std; +typedef string str; +typedef long long ll; +typedef long double ld; +typedef pair ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +vii G[100005]; +umap A[100005], B[100005]; + +ll dfs(int u, int p, int s) { + ll ret = 0; + for (auto& v : G[u]) { // Traverse children + if (v.first != p) ret += dfs(v.first, u, s + (v.second ? 1 : -1)); + } + int m = 0; // Computed largest set to merge small to large + for (auto& v : G[u]) { + if (v.first != p && A[v.first].size() + B[v.first].size() > A[m].size() + B[m].size()) m = v.first; + } + if (A[m].find(s) != A[m].end()) { + ret += B[m][s]; + B[u][s] += A[m][s]; + A[m].erase(s); + } + if (A[u].size() < A[m].size()) swap(A[u], A[m]); + if (B[u].size() < B[m].size()) swap(B[u], B[m]); + for (auto& x : A[m]) A[u][x.first] += x.second; + for (auto& x : B[m]) B[u][x.first] += x.second; + // Merge other sets + for (auto& v : G[u]) { + if (v.first != p && v.first != m) { + for (auto& x : A[v.first]) { + if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first]; + } + for (auto& x : B[v.first]) { + if (A[u].find(2 * s - x.first) != A[u].end()) ret += (ll)x.second * A[u][2 * s - x.first]; + if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first]; + } + if (A[v.first].find(s) != A[v.first].end()) { + ret += B[v.first][s]; + B[u][s] += A[v.first][s]; + A[v.first].erase(s); + } + if (A[u].size() < A[v.first].size()) swap(A[u], A[v.first]); + if (B[u].size() < B[v.first].size()) swap(B[u], B[v.first]); + for (auto& x : A[v.first]) A[u][x.first] += x.second; // Merge "A" sets + for (auto& x : B[v.first]) B[u][x.first] += x.second; // Merge "B" sets + } + } + A[u][s]++; + return ret; +} + +int main() { + init_io("yinyang"); + + int N; + cin >> N; + for (int i = 0; i < N - 1; i++) { + int A, B, t; + cin >> A >> B >> t; + G[A].emplace_back(B, t); + G[B].emplace_back(A, t); + } + cout << dfs(1, 0, 0) << endl; +} diff --git a/14/dec/gold/guard.cpp b/14/dec/gold/guard.cpp new file mode 100644 index 0000000..f1c83c8 --- /dev/null +++ b/14/dec/gold/guard.cpp @@ -0,0 +1,17 @@ +#include +#include +using namespace std; + +int ans = 0, DP[1 << 20] = { (int)1e9 }; +struct cow { int h, w, s; } C[20]; + +int main() { + int N, H; cin >> N >> H; + for (int i = 0; i < N; i++) cin >> C[i].h >> C[i].w >> C[i].s; + for (int i = 0; i < (1 << N); i++) { + int h = 0; + for (int j = 0; j < N; j++) i & 1 << j ? h += C[j].h : DP[i ^ 1 << j] = max(min(C[j].s, DP[i] - C[j].w), DP[i ^ 1 << j]); + if (h >= H) ans = max(DP[i], ans); + } + ans != 0 ? cout << ans << endl : cout << "Mark is too tall" << endl; +} diff --git a/15/dec/plat/maxflow.cpp b/15/dec/plat/maxflow.cpp new file mode 100644 index 0000000..88f3cda --- /dev/null +++ b/15/dec/plat/maxflow.cpp @@ -0,0 +1,59 @@ +#include +#include +#include +#include +using namespace std; + +int N, ans = 0, pre[50005], d[50005] = { 0 }, L[20][50005] = { 0 }; +vector G[50005]; + +void dfs(int u, int p) { + d[u] = d[p] + 1; + L[0][u] = p; + for (int i = 0; (1 << i) < N; i++) if (L[i][u]) L[i + 1][u] = L[i][L[i][u]]; + for (int 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 = log2(N); i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[i][v]; + if (u == v) return u; + for (int i = log2(N); i >= 0; i--) if (L[i][u] && L[i][u] != L[i][v]) u = L[i][u], v = L[i][v]; + return L[0][u]; +} + +void solve(int u, int p) { + for (int v : G[u]) { + if (v != p) { + solve(v, u); + pre[u] += pre[v]; + } + } + ans = max(pre[u], ans); +} + +int main() { + ifstream cin("maxflow.in"); + ofstream cout("maxflow.out"); + + int K; + cin >> N >> K; + for (int i = 0; i < N - 1; i++) { + int x, y; + cin >> x >> y; + G[x].push_back(y); + G[y].push_back(x); + } + + dfs(1, 0); + + while (K--) { + int s, t; + cin >> s >> t; + pre[s]++, pre[t]++; + pre[L[0][lca(s, t)]]--, pre[lca(s, t)]--; + } + + solve(1, 0); + cout << ans << endl; +} diff --git a/15/open/gold/googol.py b/15/open/gold/googol.py new file mode 100644 index 0000000..5eeb3be --- /dev/null +++ b/15/open/gold/googol.py @@ -0,0 +1,12 @@ +def solve(u, d): + print(u) + a, b = map(int, input().split()) + if b == 0: + return (a > 0) + 1 + if d == -1: + d = 2 * solve(a, -1) + 1 + d = d - 1 + return (d >> 1) + solve(a if d % 2 == 1 else b, (d >> 1) + (d % 2)) + 1 + +ans = solve(1, -1); +print("Answer", ans); diff --git a/16/dec/plat/triangles.cpp b/16/dec/plat/triangles.cpp new file mode 100644 index 0000000..1a2fdd9 --- /dev/null +++ b/16/dec/plat/triangles.cpp @@ -0,0 +1,113 @@ +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long ll; +typedef pair ii; +typedef vector vi; +typedef vector vii; + +struct point { + ll x, y; + point() { x = y = 0; } + point(ll _x, ll _y) : x(_x), y(_y) {} + bool operator < (point p) const { + return (x == p.x && y < p.y) || x < p.x; + } + bool operator == (point p) const { + return x == p.x && y == p.y; + } +} T[305]; + +struct vec { + ll x, y; + vec(ll _x, ll _y) : x(_x), y(_y) {} +}; + +vec to_vec(point a, point b) { + return vec(b.x - a.x, b.y - a.y); +} + +ll dot(vec a, vec b) { + return (a.x * b.x + a.y * b.y); +} + +ll norm_sq(vec v) { + return v.x * v.x + v.y * v.y; +} + +ll cross(vec a, vec b) { + return a.x * b.y - a.y * b.x; +} + +bool ccw(point p, point q, point r) { + return cross(to_vec(p, q), to_vec(p, r)) > 0; +} + +struct line { ll a, b, c; }; + +line to_line(point p1, point p2) { + return { p2.y - p1.y, p1.x - p2.x, p1.x * p2.y - p1.y * p2.x }; +} + +class fenwick_tree { +private: vector FT; +public: + fenwick_tree(int N) { FT.assign(N + 1, 0); } + void update(int x, int val) { for (; x < FT.size(); x += x & -x) FT[x] += val; } + int query(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } + int query(int x, int y) { return query(y) - (x == 1 ? 0 : query(x - 1)); } +}; + +int ans[305] = { 0 }; + +int main() { + ifstream cin("triangles.in"); + ofstream cout("triangles.out"); + + int N; + cin >> N; + for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y; + sort(T, T + N); + + for (int i = 0; i < N - 1; i++) { + for (int j = i + 1; j < N; j++) { + line L = to_line(T[i], T[j]); + + vector> A, B; + for (int k = i + 1; k < N; k++) { + if (k != i && k != j) { + if (T[k].x * L.a + T[k].y * L.b < L.c) { + A.emplace_back(ii(k, k), T[k]); + } + } + } + + vector l, r; + int N = A.size(); + for (int i = 0; i < N; i++) { + l.emplace_back(A[i].first.first, i); + r.emplace_back(A[i].first.second, i); + } + sort(l.begin(), l.end(), [i](const ii& a, const ii& b) { return ccw(T[b.first], T[i], T[a.first]); }); + sort(r.begin(), r.end(), [j](const ii& a, const ii& b) { return ccw(T[a.first], T[j], T[b.first]); }); + for (int i = 0; i < N; i++) { + A[l[i].second].first.first = i + 1; + A[r[i].second].first.second = i + 1; + } + + sort(A.begin(), A.end()); + + fenwick_tree FT(N); + for (auto& p : A) { + ans[FT.query(p.first.second)]++; + FT.update(p.first.second, 1); + } + } + } + + for (int i = 0; i < N - 2; i++) cout << ans[i] << endl; +} diff --git a/16/open/plat/landscape.cpp b/16/open/plat/landscape.cpp new file mode 100644 index 0000000..46e8d8e --- /dev/null +++ b/16/open/plat/landscape.cpp @@ -0,0 +1,70 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +vi A, B; +priority_queue p1, p2; + +int main() { + init_io("landscape"); + + ll N, X, Y, Z, ans = 0; + cin >> N >> X >> Y >> Z; + for (int i = 0; i < N; i++) { + int A, B; + cin >> A >> B; + for (int j = A; j < B; j++) { + ll cost = X; + if (!p2.empty() && i * Z - p2.top() < X) { + cost = i * Z - p2.top(); + p2.pop(); + } + ans += cost; + p1.push(i * Z + cost); + } + for (int j = B; j < A; j++) { + ll cost = Y; + if (!p1.empty() && i * Z - p1.top() < Y) { + cost = i * Z - p1.top(); + p1.pop(); + } + ans += cost; + p2.push(i * Z + cost); + } + } + cout << ans << endl; +} diff --git a/17/feb/plat/friendcross.cpp b/17/feb/plat/friendcross.cpp new file mode 100644 index 0000000..de7c198 --- /dev/null +++ b/17/feb/plat/friendcross.cpp @@ -0,0 +1,68 @@ +#include +#include +#include +#include +#define init_io 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; +using namespace __gnu_pbds; +using namespace __gnu_cxx; +typedef string str; +typedef long long ll; +typedef long double ld; +typedef complex cd; +typedef pair ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; +typedef tree, 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); + +int N, A[100005], B[100005]; +ordered_set S[100005]; + +void update(int x, int y) { for (; x <= N; x += x & -x) S[x].insert(y); } +int query(int x, int y) { int ret = 0; for (; x > 0; x -= x & -x) ret += S[x].order_of_key(y + 1); return ret; } + +int main() { + ifstream cin("friendcross.in"); + ofstream cout("friendcross.out"); + ios_base::sync_with_stdio(false); + cin.tie(NULL); + + int K; + cin >> N >> K; + for (int i = 0; i < N; ++i) { + int a; + cin >> a; + A[a] = i + 1; + } + for (int i = 0; i < N; ++i) { + int b; + cin >> b; + B[b] = i + 1; + } + ll ans = 0; + for (int i = N - K - 1; i > 0; --i) { + update(A[i + K + 1], B[i + K + 1]); + ans += query(N, B[i]) + query(A[i], N) - 2 * query(A[i], B[i]); + } + cout << ans << endl; +} diff --git a/17/feb/plat/mincross.cpp b/17/feb/plat/mincross.cpp new file mode 100644 index 0000000..a5befd0 --- /dev/null +++ b/17/feb/plat/mincross.cpp @@ -0,0 +1,57 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long ll; +typedef pair ii; +typedef vector vi; +typedef vector vii; +constexpr auto INF = (ll)1e18; + +class fenwick_tree { +private: vector FT; +public: + fenwick_tree(int N) { FT.assign(N + 1, 0); } + void update(int x, int val) { for (; x < FT.size(); x += x & -x) FT[x] += val; } + int query(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } + int query(int x, int y) { return query(y) - (x == 1 ? 0 : query(x - 1)); } +}; + +int A[100005], B[100005], RA[100005], RB[100005]; + +int main() { + ifstream cin("mincross.in"); + ofstream cout("mincross.out"); + + int N; + cin >> N; + for (int i = 0; i < N; ++i) cin >> A[i]; + for (int i = 0; i < N; ++i) cin >> B[i]; + for (int i = 0; i < N; ++i) RA[A[i]] = i + 1; + for (int i = 0; i < N; ++i) RB[B[i]] = i + 1; + + fenwick_tree FT(N); + ll cnt = 0, ans = INF; + for (int i = 0; i < N; ++i) { + cnt += FT.query(RA[B[i]], N); + FT.update(RA[B[i]], 1); + } + for (int i = 0; i < N; ++i) { + cnt += N - 2 * RA[B[i]] + 1; + ans = min(cnt, ans); + } + for (int i = 0; i < N; ++i) { + cnt += N - 2 * RB[A[i]] + 1; + ans = min(cnt, ans); + } + cout << ans << endl; +} diff --git a/17/feb/plat/nocross.cpp b/17/feb/plat/nocross.cpp new file mode 100644 index 0000000..5ce1b7c --- /dev/null +++ b/17/feb/plat/nocross.cpp @@ -0,0 +1,57 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +using namespace std; +typedef long long ll; +typedef pair ii; +typedef vector vi; +typedef vector vii; +constexpr auto INF = (int)1e9; +constexpr auto MAXN = 100005; + +int N, A[100005], B[100005], R[100005], seg[4 * MAXN] = { 0 }; + +void update(int x, int v, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l == r) seg[n] = max(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); + seg[n] = max(seg[n << 1], seg[n << 1 | 1]); + } +} + +int query(int a, int b, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l > b || r < a) return 0; + if (l >= a && r <= b) return seg[n]; + int m = (l + r) >> 1; + return max(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1)); +} + +int main() { + ifstream cin("nocross.in"); + ofstream cout("nocross.out"); + + cin >> N; + for (int i = 0; i < N; ++i) cin >> A[i], A[i]--; + for (int i = 0; i < N; ++i) cin >> B[i], B[i]--; + for (int i = 0; i < N; ++i) R[B[i]] = i; + + for (int i = 0; i < N; ++i) { + vii u; + for (int j = max(A[i] - 4, 0); j < min(A[i] + 5, N); ++j) u.emplace_back(R[j], query(0, R[j] - 1) + 1); + for (auto q : u) update(q.first, q.second); + } + + cout << query(0, N - 1) << endl; +} diff --git a/17/open/plat/cowbasic.cpp b/17/open/plat/cowbasic.cpp new file mode 100644 index 0000000..8ef44c9 --- /dev/null +++ b/17/open/plat/cowbasic.cpp @@ -0,0 +1,103 @@ +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; +constexpr auto MOD = 1000000007; + +typedef vector matrix; + +int d = 0; +map var; // Variables +vector program; // Program +stack loop_st; // Loop stack +vector mat_st; // Matrix stack + +void mult(matrix& A, matrix& B) { // B = A * B; + matrix res(d + 1, vi(d + 1, 0)); + for (int i = 0; i <= d; i++) { + for (int j = 0; j <= d; j++) { + for (int k = 0; k <= d; k++) res[i][j] = ((ll)A[i][k] * (ll)B[k][j] + res[i][j]) % MOD; + } + } + B = res; +} + +void pow(matrix& A, int n) { // A = A ^ n + matrix res(d + 1, vi(d + 1, 0)); + for (int i = 0; i <= d; i++) res[i][i] = 1; + while (n) { + if (n % 2 == 1) mult(A, res); + mult(A, A); + n /= 2; + } + A = res; +} + +int main() { + init_io("cowbasic"); + + str input; + while (getline(cin, input)) program.push_back(input); + for (auto& line : program) { // Record variables + stringstream ss(line); + str n; ss >> n; + if (islower(n[0]) && var.find(n) == var.end()) var[n] = d++; + } + mat_st.push_back({}); + mat_st.back().resize(d + 1, vi(d + 1, 0)); + for (int i = 0; i <= d; i++) mat_st.back()[i][i] = 1; + for (auto& line : program) { // Process each line + stringstream ss(line); + str n; ss >> n; + if (islower(n[0])) { // Variable assignment + matrix M(d + 1, vi(d + 1, 0)); + for (int i = 0; i <= d; i++) { + if (i != var[n]) M[i][i] = 1; + } + str tmp; + while (ss >> tmp) { + if (islower(tmp[0])) M[var[n]][var[tmp]]++; + else if (isdigit(tmp[0])) M[var[n]][d] += stoi(tmp); + } + mult(M, mat_st.back()); + } + else if (isdigit(n[0])) { // Begin loop + mat_st.push_back({}); + mat_st.back().resize(d + 1, vi(d + 1, 0)); + for (int i = 0; i <= d; i++) mat_st.back()[i][i] = 1; + loop_st.push(stoi(n)); + } + else if (n[0] == '}') { // End loop + pow(mat_st.back(), loop_st.top()); + mult(mat_st.back(), mat_st[mat_st.size() - 2]); + mat_st.pop_back(); + loop_st.pop(); + } + else { // Return + ss >> n; + cout << mat_st.back()[var[n]][d] << endl; + } + } +} diff --git a/18/dec/plat/balance.cpp b/18/dec/plat/balance.cpp new file mode 100644 index 0000000..154adbe --- /dev/null +++ b/18/dec/plat/balance.cpp @@ -0,0 +1,62 @@ +#define _CRT_SECURE_NO_WARNINGS +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +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 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 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/dec/plat/itout.cpp b/18/dec/plat/itout.cpp new file mode 100644 index 0000000..ce77c87 --- /dev/null +++ b/18/dec/plat/itout.cpp @@ -0,0 +1,99 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector 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/feb/plat/gymnasts.cpp b/18/feb/plat/gymnasts.cpp new file mode 100644 index 0000000..8904cbf --- /dev/null +++ b/18/feb/plat/gymnasts.cpp @@ -0,0 +1,97 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(0) +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +template struct FF { + ll val; + + FF(const ll x = 0) { val = (x % p + p) % p; } + + bool operator==(const FF

& other) const { return val == other.val; } + bool operator!=(const FF

& other) const { return val != other.val; } + + FF operator+() const { return val; } + FF operator-() const { return -val; } + + FF& operator+=(const FF

& other) { val = (val + other.val) % p; return *this; } + FF& operator-=(const FF

& other) { *this += -other; return *this; } + FF& operator*=(const FF

& other) { val = (val * other.val) % p; return *this; } + FF& operator/=(const FF

& other) { *this *= other.inv(); return *this; } + + FF operator+(const FF

& other) const { return FF(*this) += other; } + FF operator-(const FF

& other) const { return FF(*this) -= other; } + FF operator*(const FF

& other) const { return FF(*this) *= other; } + FF operator/(const FF

& other) const { return FF(*this) /= other; } + + static FF

pow(const FF

& a, ll b) { + if (!b) return 1; + return pow(a * a, b >> 1) * (b & 1 ? a : 1); + } + + FF

pow(const ll b) const { return pow(*this, b); } + FF

inv() const { return pow(p - 2); } +}; + +template FF

operator+(const ll lhs, const FF

& rhs) { return FF

(lhs) += rhs; } +template FF

operator-(const ll lhs, const FF

& rhs) { return FF

(lhs) -= rhs; } +template FF

operator*(const ll lhs, const FF

& rhs) { return FF

(lhs) *= rhs; } +template FF

operator/(const ll lhs, const FF

& rhs) { return FF

(lhs) /= rhs; } + +typedef FF<1000000007> MODint; + + +MODint phi(ll n) { + MODint ret = n; + for (ll p = 2; p * p <= n; p++) { + if (n % p == 0) ret -= ret / p; + while (n % p == 0) n /= p; + } + if (n > 1) ret -= ret / n; + return ret; +} + +int main() { + init_io("gymnasts"); + + ll N; + cin >> N; + MODint ans = phi(N) + 1; + for (ll i = 2; i * i <= N; i++) { + if (N % i == 0) ans += (MODint(2).pow(i) - 1) * phi(N / i) + (i * i < N) * (MODint(2).pow(N / i) - 1) * phi(i); + } + cout << ans.val << endl; +} diff --git a/18/feb/plat/newbarn.cpp b/18/feb/plat/newbarn.cpp new file mode 100644 index 0000000..e702480 --- /dev/null +++ b/18/feb/plat/newbarn.cpp @@ -0,0 +1,78 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +int S[100005], D[100005], L[100005][16] = { 0 }; +ii P[100005]; + +int lca(int u, int v) { + if (D[u] > D[v]) swap(u, v); + for (int i = 15; i >= 0; i--) if (D[v] - (1 << i) >= D[u]) v = L[v][i]; + if (u == v) return u; + for (int i = 15; 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]; +} + +inline int dist(int u, int v) { return D[u] + D[v] - 2 * D[lca(u, v)]; } + +int main() { + init_io("newbarn"); + + int Q; + cin >> Q; + int u = 0, s = 0; + while (Q--) { + char c; + cin >> c; + if (c == 'B') { + int p; + cin >> p; + u++; + D[u] = (p != -1 ? D[p] + 1 : 0); + S[u] = (p != -1 ? S[p] : s++); + for (int v = p, i = 0; v > 0 && i < 16; v = L[v][i++]) L[u][i] = v; + if (p != -1) { + if (dist(u, P[S[u]].first) > dist(P[S[u]].first, P[S[u]].second)) P[S[u]].second = u; + else if (dist(u, P[S[u]].second) > dist(P[S[u]].first, P[S[u]].second)) P[S[u]].first = u; + } + else P[S[u]] = ii(u, u); + } + else { + int k; + cin >> k; + cout << max(dist(k, P[S[k]].first), dist(k, P[S[k]].second)) << endl; + } + } +} \ No newline at end of file diff --git a/18/feb/plat/newbarn_naive.cpp b/18/feb/plat/newbarn_naive.cpp new file mode 100644 index 0000000..86a3cd5 --- /dev/null +++ b/18/feb/plat/newbarn_naive.cpp @@ -0,0 +1,72 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +// Although this algorithm is O(n^2) +// It can solve 8 / 10 test cases +// It is also easy to code +int P[100005], A[100005], B[100005]; + +int main() { + init_io("newbarn"); + + int Q; + cin >> Q; + int u = 0; + while (Q--) { + char c; + cin >> c; + if (c == 'B') { + cin >> P[++u]; + A[u] = B[u] = 0; + for (int v = u, h = 1; P[v] != -1 && B[P[v]] < h; v = P[v], h++) { + if (A[P[v]] < h) A[P[v]] = h; + else { B[P[v]] = h; break; } + } + } + else { + int k; + cin >> k; + int ans = A[k]; + for (int v = k, h = 1; P[v] != -1; v = P[v], h++) { + if (A[P[v]] == A[v] + 1) ans = max(B[P[v]] + h, ans); + else ans = max(A[P[v]] + h, ans); + } + cout << ans << '\n'; + } + } +} diff --git a/18/open/plat/sort.cpp b/18/open/plat/sort.cpp new file mode 100644 index 0000000..8e7a49a --- /dev/null +++ b/18/open/plat/sort.cpp @@ -0,0 +1,161 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +template class fenwick_tree { +private: vector FT; +public: + fenwick_tree(int N) { FT.assign(N + 1, 0); } + void clear() { FT.assign(FT.size(), 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) - (x == 1 ? 0 : query(x - 1)); } +}; + +template< typename T > class seg_tree { +private: + int N; + vector seg, tmp; +public: + seg_tree(int size) { + N = size; + seg.resize(4 * N, 0); + tmp.resize(4 * N, 0); + } + seg_tree(int size, T A[]) { + N = size; + seg.resize(4 * N); + tmp.resize(4 * N); + build(A); + } + seg_tree(vector& A) { + N = A.size(); + seg.resize(4 * N); + tmp.resize(4 * N); + build(A); + } + void clear() { seg.assign(4 * N, 0); } + void pull(int n) { seg[n] = max(seg[n << 1], seg[n << 1 | 1]); } + void push(int l, int r, int n) { + seg[n] += tmp[n]; + if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n]; + tmp[n] = 0; + } + void build(T A[], int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l == r) seg[n] = A[l]; + else { + int m = (l + r) >> 1; + build(A, l, m, n << 1), build(A, m + 1, r, n << 1 | 1); + pull(n); + } + } + void build(vector& A, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l == r) seg[n] = A[l]; + else { + int m = (l + r) >> 1; + build(A, l, m, n << 1); + build(A, m + 1, r, n << 1 | 1); + pull(n); + } + } + void update(int x, T v, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l == r) seg[n] += v; + 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, T v, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + push(n, l, r); + if (l > b || r < a) return; + if (l >= a && r <= b) { + tmp[n] = v; + push(n, l, r); + } + else { + int m = (l + r) >> 1; + update_range(a, b, v, l, m, n << 1), update_range(a, b, v, m + 1, r, n << 1 | 1); + pull(n); + } + } + T query(int a, int b, int l = 0, int r = -1, int n = 1) { + if (r == -1) r = N - 1; + if (l > b || r < a) return 0; + push(n, l, r); + if (l >= a && r <= b) return seg[n]; + int m = (l + r) >> 1; + return max(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1)); + } +}; + +int A[100005], C[100005] = { 0 }; + +int main() { + init_io("sort"); + + int N; + cin >> N; + for (int i = 0; i < N; i++) cin >> A[i]; + vector tmp; + for (int i = 0; i < N; i++) tmp.emplace_back(A[i], i); + sort(tmp.begin(), tmp.end()); + for (int i = 0; i < N; i++) A[tmp[i].second] = i; + + ll ans = 0; + fenwick_tree FT(N); + seg_tree seg(N); + for (int i = 0; i < N; i++) { + ans += FT.query(A[i], N - 1); + FT.update(A[i], 1); + } + for (int i = 0; i < N; i++) seg.update(A[i], i); + for (int i = 0; i < N; i++) { + int q = seg.query(0, A[i]); + if (i != q) C[i]++, C[q]--, ans++; + } + FT.clear(); + for (int i = N - 1; i >= 0; i--) { + ans += (ll)C[i] * FT.query(A[i], N - 1); + FT.update(A[i], 1); + } + cout << (ans ? ans : N) << endl; +} diff --git a/19/dec/gold/cowmbat.cpp b/19/dec/gold/cowmbat.cpp new file mode 100644 index 0000000..e224936 --- /dev/null +++ b/19/dec/gold/cowmbat.cpp @@ -0,0 +1,48 @@ +#include +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/dec/gold/milkvisits.cpp b/19/dec/gold/milkvisits.cpp new file mode 100644 index 0000000..d02c1bc --- /dev/null +++ b/19/dec/gold/milkvisits.cpp @@ -0,0 +1,70 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair ii; + +int N, M, T[100001], d[100001] = { 0 }, L[100001][20]; +vector G[100001]; +bitset<100001> ans; +pair q[100001]; +unordered_set 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>& S) { + for (auto& v : G[u]) { + if (v != p) { + unordered_map> 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> 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/dec/gold/pump.cpp b/19/dec/gold/pump.cpp new file mode 100644 index 0000000..20beb76 --- /dev/null +++ b/19/dec/gold/pump.cpp @@ -0,0 +1,46 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; +typedef vector vi; +typedef vector vii; +constexpr int INF = 1e9; + +vector> 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> 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/dec/plat/snowcow.cpp b/19/dec/plat/snowcow.cpp new file mode 100644 index 0000000..b4df8bd --- /dev/null +++ b/19/dec/plat/snowcow.cpp @@ -0,0 +1,127 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#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 ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector 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 G[100005]; +set 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/open/plat/boxes.cpp b/19/open/plat/boxes.cpp new file mode 100644 index 0000000..75695b9 --- /dev/null +++ b/19/open/plat/boxes.cpp @@ -0,0 +1,75 @@ +#include +#include "grader.h" +using namespace std; +typedef pair ii; +typedef vector vi; +typedef vector 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); + } +} diff --git a/20/feb/gold/deleg.cpp b/20/feb/gold/deleg.cpp new file mode 100644 index 0000000..ee9144f --- /dev/null +++ b/20/feb/gold/deleg.cpp @@ -0,0 +1,66 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair ii; + +int d[100001] = { 0 }; +vector G[100001]; + +ii dfs(int u, int p) { + d[u] = d[p] + 1; + vector 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 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/20/feb/gold/timeline.cpp b/20/feb/gold/timeline.cpp new file mode 100644 index 0000000..6a9c217 --- /dev/null +++ b/20/feb/gold/timeline.cpp @@ -0,0 +1,37 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair ii; + +int S[100001]; +vector 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, greater> 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/20/feb/plat/help.cpp b/20/feb/plat/help.cpp new file mode 100644 index 0000000..e6ae965 --- /dev/null +++ b/20/feb/plat/help.cpp @@ -0,0 +1,116 @@ +#include +#include +#include +#include +#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 cd; +typedef pair ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; +typedef tree, 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/20/jan/gold/boards.cpp b/20/jan/gold/boards.cpp new file mode 100644 index 0000000..812c959 --- /dev/null +++ b/20/jan/gold/boards.cpp @@ -0,0 +1,50 @@ +#include +#define f first +#define s second +using namespace std; +typedef pair 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 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> 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/20/jan/gold/threesum.cpp b/20/jan/gold/threesum.cpp new file mode 100644 index 0000000..21e266c --- /dev/null +++ b/20/jan/gold/threesum.cpp @@ -0,0 +1,40 @@ +#include +#define f first +#define s second +using namespace std; +typedef long long ll; +typedef pair ii; +constexpr int MAX = 1e6; + +int A[5005], cnt[5005] = { 0 }, M[2000002]; +ll ans[100001] = { 0 }; +vector> 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& a, const pair& 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/20/jan/gold/time.cpp b/20/jan/gold/time.cpp new file mode 100644 index 0000000..fd3b8cf --- /dev/null +++ b/20/jan/gold/time.cpp @@ -0,0 +1,35 @@ +#include +using namespace std; + +int m[1001], DP[1001][1001]; +vector 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/20/jan/plat/nondec.cpp b/20/jan/plat/nondec.cpp new file mode 100644 index 0000000..2084a05 --- /dev/null +++ b/20/jan/plat/nondec.cpp @@ -0,0 +1,108 @@ +#include +#include +#include +#include +#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 cd; +typedef pair ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; +typedef tree, 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>& 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> 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> 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/20/open/gold/exercise.cpp b/20/open/gold/exercise.cpp new file mode 100644 index 0000000..7e8ba80 --- /dev/null +++ b/20/open/gold/exercise.cpp @@ -0,0 +1,35 @@ +#include +using namespace std; +typedef long long ll; + +int sieve_size; +bitset<10000001> bs; +vector 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/20/open/gold/fcolor.cpp b/20/open/gold/fcolor.cpp new file mode 100644 index 0000000..5a3879d --- /dev/null +++ b/20/open/gold/fcolor.cpp @@ -0,0 +1,38 @@ +#include +using namespace std; + +int cnt = 0, c[200002], p[200002], ans[200002]; +bitset<200002> vis; +vector 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/20/open/gold/haircut.cpp b/20/open/gold/haircut.cpp new file mode 100644 index 0000000..0e93c45 --- /dev/null +++ b/20/open/gold/haircut.cpp @@ -0,0 +1,59 @@ +#include +using namespace std; +typedef long long ll; + +template class fenwick_tree { +private: vector 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 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/20/open/plat/sprinklers2.cpp b/20/open/plat/sprinklers2.cpp new file mode 100644 index 0000000..fd2fe5a --- /dev/null +++ b/20/open/plat/sprinklers2.cpp @@ -0,0 +1,68 @@ +#include +#include +#include +#include +#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 cd; +typedef pair ii; typedef pair pl; typedef pair pd; +typedef vector vi; typedef vector vl; typedef vector vd; +typedef vector vii; typedef vector vpl; typedef vector vpd; +typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; +typedef tree, 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'; +} diff --git a/2007/November/Gold/telewire.cpp b/2007/November/Gold/telewire.cpp deleted file mode 100644 index e68ae69..0000000 --- a/2007/November/Gold/telewire.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#include -#include -using namespace std; -constexpr auto INF = (int)1e9; - -int main() { - int N, C, H, A[105], B[105], DP[105]; - cin >> N >> C; - for (int i = 0; i < N; i++) { cin >> H; - for (int j = 0; j <= 100; j++) DP[j] = (j < H ? INF : (j - H) * (j - H) + (i > 0) * min(A[j] + C * j, B[j] - C * j)); - for (int j = 0; j <= 100; j++) A[j] = min(DP[j] - C * j, (j <= 0 ? INF : A[j - 1])); - for (int j = 100; j >= 0; j--) B[j] = min(DP[j] + C * j, (j >= 100 ? INF : B[j + 1])); - } - cout << *min_element(DP, DP + 100) << endl; -} diff --git a/2011/December/Gold/photo.cpp b/2011/December/Gold/photo.cpp deleted file mode 100644 index 3492b8c..0000000 --- a/2011/December/Gold/photo.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#include -using namespace std; - -int A[5][20005]; - -int main { - int N; - cin >> N; - for (int i = 0; i < 5; i++) { - for (int j = 0; j < N; j++) cin >> A[i][j]; - } - unordered_map m[5]; - for (int i = 0; i < 5; i++) { - for (int j = 0; j < N; j++) m[i][A[i][j]] = j; - } - sort(A[0], A[0] + N, [&m](const int& a, const int& b) { - int c[2] = { 0 }; - for (int i = 0; i < 5; i++) c[m[i][a] < m[i][b]]++; - return c[0] < c[1]; - }); - for (int i = 0; i < N; i++) cout << A[0][i] << '\n'; -} diff --git a/2012/March/Gold/restack.cpp b/2012/March/Gold/restack.cpp deleted file mode 100644 index 49b325d..0000000 --- a/2012/March/Gold/restack.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#include -using namespace std; - -int main() { - ifstream cin("restack.in"); - ofstream cout("restack.out"); - int n, c = 0, ans = 0; cin >> n; - vector v; - for (int i = 0; i < n; i++) { - int a, b; cin >> a >> b; - v.push_back(c += a - b); - } - sort(v.begin(), v.end()); - for (int i = 0; i < n; i++) ans += abs(v[i] - v[n / 2]); - cout << ans << '\n'; -} diff --git a/2012/November/Gold/bbreeds.cpp b/2012/November/Gold/bbreeds.cpp deleted file mode 100644 index 9d7a745..0000000 --- a/2012/November/Gold/bbreeds.cpp +++ /dev/null @@ -1,14 +0,0 @@ -#include -#include -using namespace std; - -int main() { - string S; cin >> S; - int x = 0, DP[1005] = { 1 }; - for (auto c : S) { - if (c == '(') for (x++, int i = x; i > 0; i--) DP[i] = (DP[i - 1] + DP[i]) % 2012; - else for (x--, int i = 0; i <= x; i++) DP[i] = (DP[i] + DP[i + 1]) % 2012; - DP[x + 1] = 0; - } - cout << DP[0] << endl; -} diff --git a/2012/November/Gold/btree.cpp b/2012/November/Gold/btree.cpp deleted file mode 100644 index 16462ab..0000000 --- a/2012/November/Gold/btree.cpp +++ /dev/null @@ -1,80 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -int L[40005]; -vi G[40005]; -map A[40005]; -map> B[40005]; - -int dfs(int u, int d) { - int ret = 0; - L[u] == 1 ? A[u][d] = 1 : B[u][d] = 1; - for (auto& v : G[u]) { - ret = max(dfs(v, L[v] + d), ret); - for (auto& x : A[v]) { - if (B[u].find(2 * d - L[u] - x.first) != B[u].end()) { // Match left side with corresponding right side - ret = max(max(x.second, B[u][2 * d - L[u] - x.first]), ret); - } - } - for (auto& x : B[v]) { - if (A[u].find(2 * d - L[u] - x.first) != A[u].end()) { // Match right side with corresponding left side - ret = max(max(x.second, A[u][2 * d - L[u] - x.first]), ret); - } - } - for (auto& x : A[v]) A[u][x.first] = max(max(x.first - d, x.second), A[u][x.first]); // Merge A[v] to A[u], adjust max nesting depth accordingly - for (auto& x : B[v]) B[u][x.first] = max(max(d - x.first, x.second), B[u][x.first]); // Merge B[v] to B[u], adjust max nesting depth accordingly - A[v].clear(), B[v].clear(); - } - while (!A[u].empty() && A[u].begin()->first < d) A[u].erase(A[u].begin()); - while (!B[u].empty() && B[u].begin()->first > d) B[u].erase(B[u].begin()); - return ret; -} - -int main() { - init_io("btree"); - int N; cin >> N; - for (int i = 1; i < N; i++) { - int p; cin >> p; - G[--p].push_back(i); - } - for (int i = 0; i < N; i++) { - char c; cin >> c; - L[i] = (c == '(' ? 1 : -1); - } - cout << dfs(0, L[0]); -} diff --git a/2013/February/Gold/route.cpp b/2013/February/Gold/route.cpp deleted file mode 100644 index aab04ed..0000000 --- a/2013/February/Gold/route.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include -#include -using namespace std; -constexpr auto INF = (int)1e9; -typedef pair ii; - -int l[40005], r[40005], dl[40005] = { 0 }, dr[40005] = { 0 }; -ii E[100005]; - -int main() { - int N, M, R; - cin >> N >> M >> R; - for (int i = 0; i < N; i++) cin >> l[i]; - for (int i = 0; i < M; i++) cin >> r[i]; - for (int i = 0; i < R; i++) cin >> E[i].first >> E[i].second; - - sort(E, E + R, [](const ii& a, const ii& b) { return a.first + a.second < b.first + b.second; }); - - for (int i = 0; i < N; i++) dl[i] = l[i]; - for (int i = 0; i < M; i++) dr[i] = r[i]; - - for (int i = 0; i < R; i++) { - int u = E[i].first, v = E[i].second, a = dl[--u], b = dr[--v]; - dl[u] = max(l[u] + b, dl[u]); - dr[v] = max(r[v] + a, dr[v]); - } - - cout << max(*max_element(dl, dl + N), *max_element(dr, dr + N)) << endl; -} diff --git a/2013/November/Gold/nochange.cpp b/2013/November/Gold/nochange.cpp deleted file mode 100644 index ad34b80..0000000 --- a/2013/November/Gold/nochange.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include -#include -using namespace std; - -int v[20], p[100005] = { 0 }, DP[1 << 16]; - -inline int sum(int i, int j) { return p[j + 1] - p[i]; } - -int main() { - int K, N; cin >> K >> N; - for (int i = 0; i < K; i++) cin >> v[i]; - for (int i = 0; i < N; i++) { - int c; cin >> c; - p[i + 1] = c + p[i]; - } - - for (int i = 0; i < (1 << K); i++) if (DP[i] < N) { - for (int j = 0; j < K; j++) if ((i & 1 << j) == 0) { - int l = DP[i], h = N; - while (l + 1 < h) { - int m = (l + h) / 2; - sum(DP[i], m) > v[j] ? h = m : l = m; - } - DP[i ^ 1 << j] = max(l + 1, DP[i ^ 1 << j]); - } - } - - int ans = -1; - for (int i = 0; i < (1 << K); i++) { - if (DP[i] == N) { - int sum = 0; - for (int j = 0; j < K; j++) if ((i & 1 << j) == 0) sum += v[j]; - ans = max(sum, ans); - } - } - cout << ans << endl; -} diff --git a/2013/US Open/Gold/yinyang.cpp b/2013/US Open/Gold/yinyang.cpp deleted file mode 100644 index 9ce4aec..0000000 --- a/2013/US Open/Gold/yinyang.cpp +++ /dev/null @@ -1,97 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 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)) -#define uset unordered_set -#define umap unordered_map -using namespace std; -typedef string str; -typedef long long ll; -typedef long double ld; -typedef pair ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -vii G[100005]; -umap A[100005], B[100005]; - -ll dfs(int u, int p, int s) { - ll ret = 0; - for (auto& v : G[u]) { // Traverse children - if (v.first != p) ret += dfs(v.first, u, s + (v.second ? 1 : -1)); - } - int m = 0; // Computed largest set to merge small to large - for (auto& v : G[u]) { - if (v.first != p && A[v.first].size() + B[v.first].size() > A[m].size() + B[m].size()) m = v.first; - } - if (A[m].find(s) != A[m].end()) { - ret += B[m][s]; - B[u][s] += A[m][s]; - A[m].erase(s); - } - if (A[u].size() < A[m].size()) swap(A[u], A[m]); - if (B[u].size() < B[m].size()) swap(B[u], B[m]); - for (auto& x : A[m]) A[u][x.first] += x.second; - for (auto& x : B[m]) B[u][x.first] += x.second; - // Merge other sets - for (auto& v : G[u]) { - if (v.first != p && v.first != m) { - for (auto& x : A[v.first]) { - if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first]; - } - for (auto& x : B[v.first]) { - if (A[u].find(2 * s - x.first) != A[u].end()) ret += (ll)x.second * A[u][2 * s - x.first]; - if (B[u].find(2 * s - x.first) != B[u].end()) ret += (ll)x.second * B[u][2 * s - x.first]; - } - if (A[v.first].find(s) != A[v.first].end()) { - ret += B[v.first][s]; - B[u][s] += A[v.first][s]; - A[v.first].erase(s); - } - if (A[u].size() < A[v.first].size()) swap(A[u], A[v.first]); - if (B[u].size() < B[v.first].size()) swap(B[u], B[v.first]); - for (auto& x : A[v.first]) A[u][x.first] += x.second; // Merge "A" sets - for (auto& x : B[v.first]) B[u][x.first] += x.second; // Merge "B" sets - } - } - A[u][s]++; - return ret; -} - -int main() { - init_io("yinyang"); - - int N; - cin >> N; - for (int i = 0; i < N - 1; i++) { - int A, B, t; - cin >> A >> B >> t; - G[A].emplace_back(B, t); - G[B].emplace_back(A, t); - } - cout << dfs(1, 0, 0) << endl; -} diff --git a/2014/December/Gold/guard.cpp b/2014/December/Gold/guard.cpp deleted file mode 100644 index f1c83c8..0000000 --- a/2014/December/Gold/guard.cpp +++ /dev/null @@ -1,17 +0,0 @@ -#include -#include -using namespace std; - -int ans = 0, DP[1 << 20] = { (int)1e9 }; -struct cow { int h, w, s; } C[20]; - -int main() { - int N, H; cin >> N >> H; - for (int i = 0; i < N; i++) cin >> C[i].h >> C[i].w >> C[i].s; - for (int i = 0; i < (1 << N); i++) { - int h = 0; - for (int j = 0; j < N; j++) i & 1 << j ? h += C[j].h : DP[i ^ 1 << j] = max(min(C[j].s, DP[i] - C[j].w), DP[i ^ 1 << j]); - if (h >= H) ans = max(DP[i], ans); - } - ans != 0 ? cout << ans << endl : cout << "Mark is too tall" << endl; -} diff --git a/2015/December/Platinum/maxflow.cpp b/2015/December/Platinum/maxflow.cpp deleted file mode 100644 index 88f3cda..0000000 --- a/2015/December/Platinum/maxflow.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include -#include -#include -#include -using namespace std; - -int N, ans = 0, pre[50005], d[50005] = { 0 }, L[20][50005] = { 0 }; -vector G[50005]; - -void dfs(int u, int p) { - d[u] = d[p] + 1; - L[0][u] = p; - for (int i = 0; (1 << i) < N; i++) if (L[i][u]) L[i + 1][u] = L[i][L[i][u]]; - for (int 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 = log2(N); i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[i][v]; - if (u == v) return u; - for (int i = log2(N); i >= 0; i--) if (L[i][u] && L[i][u] != L[i][v]) u = L[i][u], v = L[i][v]; - return L[0][u]; -} - -void solve(int u, int p) { - for (int v : G[u]) { - if (v != p) { - solve(v, u); - pre[u] += pre[v]; - } - } - ans = max(pre[u], ans); -} - -int main() { - ifstream cin("maxflow.in"); - ofstream cout("maxflow.out"); - - int K; - cin >> N >> K; - for (int i = 0; i < N - 1; i++) { - int x, y; - cin >> x >> y; - G[x].push_back(y); - G[y].push_back(x); - } - - dfs(1, 0); - - while (K--) { - int s, t; - cin >> s >> t; - pre[s]++, pre[t]++; - pre[L[0][lca(s, t)]]--, pre[lca(s, t)]--; - } - - solve(1, 0); - cout << ans << endl; -} diff --git a/2015/US Open/Gold/googol.py b/2015/US Open/Gold/googol.py deleted file mode 100644 index 5eeb3be..0000000 --- a/2015/US Open/Gold/googol.py +++ /dev/null @@ -1,12 +0,0 @@ -def solve(u, d): - print(u) - a, b = map(int, input().split()) - if b == 0: - return (a > 0) + 1 - if d == -1: - d = 2 * solve(a, -1) + 1 - d = d - 1 - return (d >> 1) + solve(a if d % 2 == 1 else b, (d >> 1) + (d % 2)) + 1 - -ans = solve(1, -1); -print("Answer", ans); diff --git a/2016/December/Platinum/triangles.cpp b/2016/December/Platinum/triangles.cpp deleted file mode 100644 index 1a2fdd9..0000000 --- a/2016/December/Platinum/triangles.cpp +++ /dev/null @@ -1,113 +0,0 @@ -#include -#include -#include -#include -#include -#include -using namespace std; -typedef long long ll; -typedef pair ii; -typedef vector vi; -typedef vector vii; - -struct point { - ll x, y; - point() { x = y = 0; } - point(ll _x, ll _y) : x(_x), y(_y) {} - bool operator < (point p) const { - return (x == p.x && y < p.y) || x < p.x; - } - bool operator == (point p) const { - return x == p.x && y == p.y; - } -} T[305]; - -struct vec { - ll x, y; - vec(ll _x, ll _y) : x(_x), y(_y) {} -}; - -vec to_vec(point a, point b) { - return vec(b.x - a.x, b.y - a.y); -} - -ll dot(vec a, vec b) { - return (a.x * b.x + a.y * b.y); -} - -ll norm_sq(vec v) { - return v.x * v.x + v.y * v.y; -} - -ll cross(vec a, vec b) { - return a.x * b.y - a.y * b.x; -} - -bool ccw(point p, point q, point r) { - return cross(to_vec(p, q), to_vec(p, r)) > 0; -} - -struct line { ll a, b, c; }; - -line to_line(point p1, point p2) { - return { p2.y - p1.y, p1.x - p2.x, p1.x * p2.y - p1.y * p2.x }; -} - -class fenwick_tree { -private: vector FT; -public: - fenwick_tree(int N) { FT.assign(N + 1, 0); } - void update(int x, int val) { for (; x < FT.size(); x += x & -x) FT[x] += val; } - int query(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } - int query(int x, int y) { return query(y) - (x == 1 ? 0 : query(x - 1)); } -}; - -int ans[305] = { 0 }; - -int main() { - ifstream cin("triangles.in"); - ofstream cout("triangles.out"); - - int N; - cin >> N; - for (int i = 0; i < N; i++) cin >> T[i].x >> T[i].y; - sort(T, T + N); - - for (int i = 0; i < N - 1; i++) { - for (int j = i + 1; j < N; j++) { - line L = to_line(T[i], T[j]); - - vector> A, B; - for (int k = i + 1; k < N; k++) { - if (k != i && k != j) { - if (T[k].x * L.a + T[k].y * L.b < L.c) { - A.emplace_back(ii(k, k), T[k]); - } - } - } - - vector l, r; - int N = A.size(); - for (int i = 0; i < N; i++) { - l.emplace_back(A[i].first.first, i); - r.emplace_back(A[i].first.second, i); - } - sort(l.begin(), l.end(), [i](const ii& a, const ii& b) { return ccw(T[b.first], T[i], T[a.first]); }); - sort(r.begin(), r.end(), [j](const ii& a, const ii& b) { return ccw(T[a.first], T[j], T[b.first]); }); - for (int i = 0; i < N; i++) { - A[l[i].second].first.first = i + 1; - A[r[i].second].first.second = i + 1; - } - - sort(A.begin(), A.end()); - - fenwick_tree FT(N); - for (auto& p : A) { - ans[FT.query(p.first.second)]++; - FT.update(p.first.second, 1); - } - } - } - - for (int i = 0; i < N - 2; i++) cout << ans[i] << endl; -} diff --git a/2016/US Open/Platinum/landscape.cpp b/2016/US Open/Platinum/landscape.cpp deleted file mode 100644 index 46e8d8e..0000000 --- a/2016/US Open/Platinum/landscape.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -vi A, B; -priority_queue p1, p2; - -int main() { - init_io("landscape"); - - ll N, X, Y, Z, ans = 0; - cin >> N >> X >> Y >> Z; - for (int i = 0; i < N; i++) { - int A, B; - cin >> A >> B; - for (int j = A; j < B; j++) { - ll cost = X; - if (!p2.empty() && i * Z - p2.top() < X) { - cost = i * Z - p2.top(); - p2.pop(); - } - ans += cost; - p1.push(i * Z + cost); - } - for (int j = B; j < A; j++) { - ll cost = Y; - if (!p1.empty() && i * Z - p1.top() < Y) { - cost = i * Z - p1.top(); - p1.pop(); - } - ans += cost; - p2.push(i * Z + cost); - } - } - cout << ans << endl; -} diff --git a/2017/February/Platinum/friendcross.cpp b/2017/February/Platinum/friendcross.cpp deleted file mode 100644 index de7c198..0000000 --- a/2017/February/Platinum/friendcross.cpp +++ /dev/null @@ -1,68 +0,0 @@ -#include -#include -#include -#include -#define init_io 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; -using namespace __gnu_pbds; -using namespace __gnu_cxx; -typedef string str; -typedef long long ll; -typedef long double ld; -typedef complex cd; -typedef pair ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; -typedef tree, 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); - -int N, A[100005], B[100005]; -ordered_set S[100005]; - -void update(int x, int y) { for (; x <= N; x += x & -x) S[x].insert(y); } -int query(int x, int y) { int ret = 0; for (; x > 0; x -= x & -x) ret += S[x].order_of_key(y + 1); return ret; } - -int main() { - ifstream cin("friendcross.in"); - ofstream cout("friendcross.out"); - ios_base::sync_with_stdio(false); - cin.tie(NULL); - - int K; - cin >> N >> K; - for (int i = 0; i < N; ++i) { - int a; - cin >> a; - A[a] = i + 1; - } - for (int i = 0; i < N; ++i) { - int b; - cin >> b; - B[b] = i + 1; - } - ll ans = 0; - for (int i = N - K - 1; i > 0; --i) { - update(A[i + K + 1], B[i + K + 1]); - ans += query(N, B[i]) + query(A[i], N) - 2 * query(A[i], B[i]); - } - cout << ans << endl; -} diff --git a/2017/February/Platinum/mincross.cpp b/2017/February/Platinum/mincross.cpp deleted file mode 100644 index a5befd0..0000000 --- a/2017/February/Platinum/mincross.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -using namespace std; -typedef long long ll; -typedef pair ii; -typedef vector vi; -typedef vector vii; -constexpr auto INF = (ll)1e18; - -class fenwick_tree { -private: vector FT; -public: - fenwick_tree(int N) { FT.assign(N + 1, 0); } - void update(int x, int val) { for (; x < FT.size(); x += x & -x) FT[x] += val; } - int query(int x) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x]; return ret; } - int query(int x, int y) { return query(y) - (x == 1 ? 0 : query(x - 1)); } -}; - -int A[100005], B[100005], RA[100005], RB[100005]; - -int main() { - ifstream cin("mincross.in"); - ofstream cout("mincross.out"); - - int N; - cin >> N; - for (int i = 0; i < N; ++i) cin >> A[i]; - for (int i = 0; i < N; ++i) cin >> B[i]; - for (int i = 0; i < N; ++i) RA[A[i]] = i + 1; - for (int i = 0; i < N; ++i) RB[B[i]] = i + 1; - - fenwick_tree FT(N); - ll cnt = 0, ans = INF; - for (int i = 0; i < N; ++i) { - cnt += FT.query(RA[B[i]], N); - FT.update(RA[B[i]], 1); - } - for (int i = 0; i < N; ++i) { - cnt += N - 2 * RA[B[i]] + 1; - ans = min(cnt, ans); - } - for (int i = 0; i < N; ++i) { - cnt += N - 2 * RB[A[i]] + 1; - ans = min(cnt, ans); - } - cout << ans << endl; -} diff --git a/2017/February/Platinum/nocross.cpp b/2017/February/Platinum/nocross.cpp deleted file mode 100644 index 5ce1b7c..0000000 --- a/2017/February/Platinum/nocross.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -using namespace std; -typedef long long ll; -typedef pair ii; -typedef vector vi; -typedef vector vii; -constexpr auto INF = (int)1e9; -constexpr auto MAXN = 100005; - -int N, A[100005], B[100005], R[100005], seg[4 * MAXN] = { 0 }; - -void update(int x, int v, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l == r) seg[n] = max(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); - seg[n] = max(seg[n << 1], seg[n << 1 | 1]); - } -} - -int query(int a, int b, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l > b || r < a) return 0; - if (l >= a && r <= b) return seg[n]; - int m = (l + r) >> 1; - return max(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1)); -} - -int main() { - ifstream cin("nocross.in"); - ofstream cout("nocross.out"); - - cin >> N; - for (int i = 0; i < N; ++i) cin >> A[i], A[i]--; - for (int i = 0; i < N; ++i) cin >> B[i], B[i]--; - for (int i = 0; i < N; ++i) R[B[i]] = i; - - for (int i = 0; i < N; ++i) { - vii u; - for (int j = max(A[i] - 4, 0); j < min(A[i] + 5, N); ++j) u.emplace_back(R[j], query(0, R[j] - 1) + 1); - for (auto q : u) update(q.first, q.second); - } - - cout << query(0, N - 1) << endl; -} diff --git a/2017/US Open/Platinum/cowbasic.cpp b/2017/US Open/Platinum/cowbasic.cpp deleted file mode 100644 index 8ef44c9..0000000 --- a/2017/US Open/Platinum/cowbasic.cpp +++ /dev/null @@ -1,103 +0,0 @@ -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; -constexpr auto MOD = 1000000007; - -typedef vector matrix; - -int d = 0; -map var; // Variables -vector program; // Program -stack loop_st; // Loop stack -vector mat_st; // Matrix stack - -void mult(matrix& A, matrix& B) { // B = A * B; - matrix res(d + 1, vi(d + 1, 0)); - for (int i = 0; i <= d; i++) { - for (int j = 0; j <= d; j++) { - for (int k = 0; k <= d; k++) res[i][j] = ((ll)A[i][k] * (ll)B[k][j] + res[i][j]) % MOD; - } - } - B = res; -} - -void pow(matrix& A, int n) { // A = A ^ n - matrix res(d + 1, vi(d + 1, 0)); - for (int i = 0; i <= d; i++) res[i][i] = 1; - while (n) { - if (n % 2 == 1) mult(A, res); - mult(A, A); - n /= 2; - } - A = res; -} - -int main() { - init_io("cowbasic"); - - str input; - while (getline(cin, input)) program.push_back(input); - for (auto& line : program) { // Record variables - stringstream ss(line); - str n; ss >> n; - if (islower(n[0]) && var.find(n) == var.end()) var[n] = d++; - } - mat_st.push_back({}); - mat_st.back().resize(d + 1, vi(d + 1, 0)); - for (int i = 0; i <= d; i++) mat_st.back()[i][i] = 1; - for (auto& line : program) { // Process each line - stringstream ss(line); - str n; ss >> n; - if (islower(n[0])) { // Variable assignment - matrix M(d + 1, vi(d + 1, 0)); - for (int i = 0; i <= d; i++) { - if (i != var[n]) M[i][i] = 1; - } - str tmp; - while (ss >> tmp) { - if (islower(tmp[0])) M[var[n]][var[tmp]]++; - else if (isdigit(tmp[0])) M[var[n]][d] += stoi(tmp); - } - mult(M, mat_st.back()); - } - else if (isdigit(n[0])) { // Begin loop - mat_st.push_back({}); - mat_st.back().resize(d + 1, vi(d + 1, 0)); - for (int i = 0; i <= d; i++) mat_st.back()[i][i] = 1; - loop_st.push(stoi(n)); - } - else if (n[0] == '}') { // End loop - pow(mat_st.back(), loop_st.top()); - mult(mat_st.back(), mat_st[mat_st.size() - 2]); - mat_st.pop_back(); - loop_st.pop(); - } - else { // Return - ss >> n; - cout << mat_st.back()[var[n]][d] << endl; - } - } -} diff --git a/2018/December/Platinum/balance.cpp b/2018/December/Platinum/balance.cpp deleted file mode 100644 index 154adbe..0000000 --- a/2018/December/Platinum/balance.cpp +++ /dev/null @@ -1,62 +0,0 @@ -#define _CRT_SECURE_NO_WARNINGS -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -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 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 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/2018/December/Platinum/itout.cpp b/2018/December/Platinum/itout.cpp deleted file mode 100644 index ce77c87..0000000 --- a/2018/December/Platinum/itout.cpp +++ /dev/null @@ -1,99 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector 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/2018/February/Platinum/gymnasts.cpp b/2018/February/Platinum/gymnasts.cpp deleted file mode 100644 index 8904cbf..0000000 --- a/2018/February/Platinum/gymnasts.cpp +++ /dev/null @@ -1,97 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(0) -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -template struct FF { - ll val; - - FF(const ll x = 0) { val = (x % p + p) % p; } - - bool operator==(const FF

& other) const { return val == other.val; } - bool operator!=(const FF

& other) const { return val != other.val; } - - FF operator+() const { return val; } - FF operator-() const { return -val; } - - FF& operator+=(const FF

& other) { val = (val + other.val) % p; return *this; } - FF& operator-=(const FF

& other) { *this += -other; return *this; } - FF& operator*=(const FF

& other) { val = (val * other.val) % p; return *this; } - FF& operator/=(const FF

& other) { *this *= other.inv(); return *this; } - - FF operator+(const FF

& other) const { return FF(*this) += other; } - FF operator-(const FF

& other) const { return FF(*this) -= other; } - FF operator*(const FF

& other) const { return FF(*this) *= other; } - FF operator/(const FF

& other) const { return FF(*this) /= other; } - - static FF

pow(const FF

& a, ll b) { - if (!b) return 1; - return pow(a * a, b >> 1) * (b & 1 ? a : 1); - } - - FF

pow(const ll b) const { return pow(*this, b); } - FF

inv() const { return pow(p - 2); } -}; - -template FF

operator+(const ll lhs, const FF

& rhs) { return FF

(lhs) += rhs; } -template FF

operator-(const ll lhs, const FF

& rhs) { return FF

(lhs) -= rhs; } -template FF

operator*(const ll lhs, const FF

& rhs) { return FF

(lhs) *= rhs; } -template FF

operator/(const ll lhs, const FF

& rhs) { return FF

(lhs) /= rhs; } - -typedef FF<1000000007> MODint; - - -MODint phi(ll n) { - MODint ret = n; - for (ll p = 2; p * p <= n; p++) { - if (n % p == 0) ret -= ret / p; - while (n % p == 0) n /= p; - } - if (n > 1) ret -= ret / n; - return ret; -} - -int main() { - init_io("gymnasts"); - - ll N; - cin >> N; - MODint ans = phi(N) + 1; - for (ll i = 2; i * i <= N; i++) { - if (N % i == 0) ans += (MODint(2).pow(i) - 1) * phi(N / i) + (i * i < N) * (MODint(2).pow(N / i) - 1) * phi(i); - } - cout << ans.val << endl; -} diff --git a/2018/February/Platinum/newbarn.cpp b/2018/February/Platinum/newbarn.cpp deleted file mode 100644 index e702480..0000000 --- a/2018/February/Platinum/newbarn.cpp +++ /dev/null @@ -1,78 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -int S[100005], D[100005], L[100005][16] = { 0 }; -ii P[100005]; - -int lca(int u, int v) { - if (D[u] > D[v]) swap(u, v); - for (int i = 15; i >= 0; i--) if (D[v] - (1 << i) >= D[u]) v = L[v][i]; - if (u == v) return u; - for (int i = 15; 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]; -} - -inline int dist(int u, int v) { return D[u] + D[v] - 2 * D[lca(u, v)]; } - -int main() { - init_io("newbarn"); - - int Q; - cin >> Q; - int u = 0, s = 0; - while (Q--) { - char c; - cin >> c; - if (c == 'B') { - int p; - cin >> p; - u++; - D[u] = (p != -1 ? D[p] + 1 : 0); - S[u] = (p != -1 ? S[p] : s++); - for (int v = p, i = 0; v > 0 && i < 16; v = L[v][i++]) L[u][i] = v; - if (p != -1) { - if (dist(u, P[S[u]].first) > dist(P[S[u]].first, P[S[u]].second)) P[S[u]].second = u; - else if (dist(u, P[S[u]].second) > dist(P[S[u]].first, P[S[u]].second)) P[S[u]].first = u; - } - else P[S[u]] = ii(u, u); - } - else { - int k; - cin >> k; - cout << max(dist(k, P[S[k]].first), dist(k, P[S[k]].second)) << endl; - } - } -} \ No newline at end of file diff --git a/2018/February/Platinum/newbarn_naive.cpp b/2018/February/Platinum/newbarn_naive.cpp deleted file mode 100644 index 86a3cd5..0000000 --- a/2018/February/Platinum/newbarn_naive.cpp +++ /dev/null @@ -1,72 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -// Although this algorithm is O(n^2) -// It can solve 8 / 10 test cases -// It is also easy to code -int P[100005], A[100005], B[100005]; - -int main() { - init_io("newbarn"); - - int Q; - cin >> Q; - int u = 0; - while (Q--) { - char c; - cin >> c; - if (c == 'B') { - cin >> P[++u]; - A[u] = B[u] = 0; - for (int v = u, h = 1; P[v] != -1 && B[P[v]] < h; v = P[v], h++) { - if (A[P[v]] < h) A[P[v]] = h; - else { B[P[v]] = h; break; } - } - } - else { - int k; - cin >> k; - int ans = A[k]; - for (int v = k, h = 1; P[v] != -1; v = P[v], h++) { - if (A[P[v]] == A[v] + 1) ans = max(B[P[v]] + h, ans); - else ans = max(A[P[v]] + h, ans); - } - cout << ans << '\n'; - } - } -} diff --git a/2018/US Open/Platinum/sort.cpp b/2018/US Open/Platinum/sort.cpp deleted file mode 100644 index 8e7a49a..0000000 --- a/2018/US Open/Platinum/sort.cpp +++ /dev/null @@ -1,161 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -constexpr auto INF = (int)1e9; -constexpr auto LINF = (ll)1e18; - -template class fenwick_tree { -private: vector FT; -public: - fenwick_tree(int N) { FT.assign(N + 1, 0); } - void clear() { FT.assign(FT.size(), 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) - (x == 1 ? 0 : query(x - 1)); } -}; - -template< typename T > class seg_tree { -private: - int N; - vector seg, tmp; -public: - seg_tree(int size) { - N = size; - seg.resize(4 * N, 0); - tmp.resize(4 * N, 0); - } - seg_tree(int size, T A[]) { - N = size; - seg.resize(4 * N); - tmp.resize(4 * N); - build(A); - } - seg_tree(vector& A) { - N = A.size(); - seg.resize(4 * N); - tmp.resize(4 * N); - build(A); - } - void clear() { seg.assign(4 * N, 0); } - void pull(int n) { seg[n] = max(seg[n << 1], seg[n << 1 | 1]); } - void push(int l, int r, int n) { - seg[n] += tmp[n]; - if (l != r) tmp[n << 1] += tmp[n], tmp[n << 1 | 1] += tmp[n]; - tmp[n] = 0; - } - void build(T A[], int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l == r) seg[n] = A[l]; - else { - int m = (l + r) >> 1; - build(A, l, m, n << 1), build(A, m + 1, r, n << 1 | 1); - pull(n); - } - } - void build(vector& A, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l == r) seg[n] = A[l]; - else { - int m = (l + r) >> 1; - build(A, l, m, n << 1); - build(A, m + 1, r, n << 1 | 1); - pull(n); - } - } - void update(int x, T v, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l == r) seg[n] += v; - 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, T v, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - push(n, l, r); - if (l > b || r < a) return; - if (l >= a && r <= b) { - tmp[n] = v; - push(n, l, r); - } - else { - int m = (l + r) >> 1; - update_range(a, b, v, l, m, n << 1), update_range(a, b, v, m + 1, r, n << 1 | 1); - pull(n); - } - } - T query(int a, int b, int l = 0, int r = -1, int n = 1) { - if (r == -1) r = N - 1; - if (l > b || r < a) return 0; - push(n, l, r); - if (l >= a && r <= b) return seg[n]; - int m = (l + r) >> 1; - return max(query(a, b, l, m, n << 1), query(a, b, m + 1, r, n << 1 | 1)); - } -}; - -int A[100005], C[100005] = { 0 }; - -int main() { - init_io("sort"); - - int N; - cin >> N; - for (int i = 0; i < N; i++) cin >> A[i]; - vector tmp; - for (int i = 0; i < N; i++) tmp.emplace_back(A[i], i); - sort(tmp.begin(), tmp.end()); - for (int i = 0; i < N; i++) A[tmp[i].second] = i; - - ll ans = 0; - fenwick_tree FT(N); - seg_tree seg(N); - for (int i = 0; i < N; i++) { - ans += FT.query(A[i], N - 1); - FT.update(A[i], 1); - } - for (int i = 0; i < N; i++) seg.update(A[i], i); - for (int i = 0; i < N; i++) { - int q = seg.query(0, A[i]); - if (i != q) C[i]++, C[q]--, ans++; - } - FT.clear(); - for (int i = N - 1; i >= 0; i--) { - ans += (ll)C[i] * FT.query(A[i], N - 1); - FT.update(A[i], 1); - } - cout << (ans ? ans : N) << endl; -} diff --git a/2019/December/Gold/cowmbat.cpp b/2019/December/Gold/cowmbat.cpp deleted file mode 100644 index e224936..0000000 --- a/2019/December/Gold/cowmbat.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include -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/2019/December/Gold/milkvisits.cpp b/2019/December/Gold/milkvisits.cpp deleted file mode 100644 index d02c1bc..0000000 --- a/2019/December/Gold/milkvisits.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair ii; - -int N, M, T[100001], d[100001] = { 0 }, L[100001][20]; -vector G[100001]; -bitset<100001> ans; -pair q[100001]; -unordered_set 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>& S) { - for (auto& v : G[u]) { - if (v != p) { - unordered_map> 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> 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/2019/December/Gold/pump.cpp b/2019/December/Gold/pump.cpp deleted file mode 100644 index 20beb76..0000000 --- a/2019/December/Gold/pump.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; -typedef vector vi; -typedef vector vii; -constexpr int INF = 1e9; - -vector> 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> 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/2019/December/Platinum/snowcow.cpp b/2019/December/Platinum/snowcow.cpp deleted file mode 100644 index b4df8bd..0000000 --- a/2019/December/Platinum/snowcow.cpp +++ /dev/null @@ -1,127 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#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 ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector 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 G[100005]; -set 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/2019/US Open/Platinum/boxes.cpp b/2019/US Open/Platinum/boxes.cpp deleted file mode 100644 index 75695b9..0000000 --- a/2019/US Open/Platinum/boxes.cpp +++ /dev/null @@ -1,75 +0,0 @@ -#include -#include "grader.h" -using namespace std; -typedef pair ii; -typedef vector vi; -typedef vector 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); - } -} diff --git a/2020/February/Gold/deleg.cpp b/2020/February/Gold/deleg.cpp deleted file mode 100644 index ee9144f..0000000 --- a/2020/February/Gold/deleg.cpp +++ /dev/null @@ -1,66 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair ii; - -int d[100001] = { 0 }; -vector G[100001]; - -ii dfs(int u, int p) { - d[u] = d[p] + 1; - vector 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 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/2020/February/Gold/timeline.cpp b/2020/February/Gold/timeline.cpp deleted file mode 100644 index 6a9c217..0000000 --- a/2020/February/Gold/timeline.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair ii; - -int S[100001]; -vector 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, greater> 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/2020/February/Platinum/help.cpp b/2020/February/Platinum/help.cpp deleted file mode 100644 index e6ae965..0000000 --- a/2020/February/Platinum/help.cpp +++ /dev/null @@ -1,116 +0,0 @@ -#include -#include -#include -#include -#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 cd; -typedef pair ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; -typedef tree, 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/2020/January/Gold/boards.cpp b/2020/January/Gold/boards.cpp deleted file mode 100644 index 812c959..0000000 --- a/2020/January/Gold/boards.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef pair 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 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> 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/2020/January/Gold/threesum.cpp b/2020/January/Gold/threesum.cpp deleted file mode 100644 index 21e266c..0000000 --- a/2020/January/Gold/threesum.cpp +++ /dev/null @@ -1,40 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -typedef long long ll; -typedef pair ii; -constexpr int MAX = 1e6; - -int A[5005], cnt[5005] = { 0 }, M[2000002]; -ll ans[100001] = { 0 }; -vector> 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& a, const pair& 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/2020/January/Gold/time.cpp b/2020/January/Gold/time.cpp deleted file mode 100644 index fd3b8cf..0000000 --- a/2020/January/Gold/time.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include -using namespace std; - -int m[1001], DP[1001][1001]; -vector 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/2020/January/Platinum/nondec.cpp b/2020/January/Platinum/nondec.cpp deleted file mode 100644 index 2084a05..0000000 --- a/2020/January/Platinum/nondec.cpp +++ /dev/null @@ -1,108 +0,0 @@ -#include -#include -#include -#include -#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 cd; -typedef pair ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; -typedef tree, 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>& 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> 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> 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/2020/US Open/Gold/exercise.cpp b/2020/US Open/Gold/exercise.cpp deleted file mode 100644 index 7e8ba80..0000000 --- a/2020/US Open/Gold/exercise.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include -using namespace std; -typedef long long ll; - -int sieve_size; -bitset<10000001> bs; -vector 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/2020/US Open/Gold/fcolor.cpp b/2020/US Open/Gold/fcolor.cpp deleted file mode 100644 index 5a3879d..0000000 --- a/2020/US Open/Gold/fcolor.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include -using namespace std; - -int cnt = 0, c[200002], p[200002], ans[200002]; -bitset<200002> vis; -vector 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/2020/US Open/Gold/haircut.cpp b/2020/US Open/Gold/haircut.cpp deleted file mode 100644 index 0e93c45..0000000 --- a/2020/US Open/Gold/haircut.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include -using namespace std; -typedef long long ll; - -template class fenwick_tree { -private: vector 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 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/2020/US Open/Platinum/sprinklers2.cpp b/2020/US Open/Platinum/sprinklers2.cpp deleted file mode 100644 index fd2fe5a..0000000 --- a/2020/US Open/Platinum/sprinklers2.cpp +++ /dev/null @@ -1,68 +0,0 @@ -#include -#include -#include -#include -#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 cd; -typedef pair ii; typedef pair pl; typedef pair pd; -typedef vector vi; typedef vector vl; typedef vector vd; -typedef vector vii; typedef vector vpl; typedef vector vpd; -typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; -typedef tree, 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'; -} -- cgit v1.2.3-70-g09d2