From 896c6ceeff605c935a5538e3d9eca40ea3c79c56 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 15 Mar 2022 20:38:51 -0500 Subject: Restructure directories AGAIN so contests from the same season are in the same directory --- 07/nov/gold/telewire.cpp | 15 ---- 11.5/dec/gold/photo.cpp | 22 ++++++ 11.5/mar/gold/restack.cpp | 16 ++++ 11/dec/gold/photo.cpp | 22 ------ 12.5/feb/gold/route.cpp | 29 ++++++++ 12.5/nov/gold/bbreeds.cpp | 14 ++++ 12.5/nov/gold/btree.cpp | 80 ++++++++++++++++++++ 12.5/open/gold/yinyang.cpp | 97 ++++++++++++++++++++++++ 12/mar/gold/restack.cpp | 16 ---- 12/nov/gold/bbreeds.cpp | 14 ---- 12/nov/gold/btree.cpp | 80 -------------------- 13.5/nov/gold/nochange.cpp | 37 +++++++++ 13/feb/gold/route.cpp | 29 -------- 13/nov/gold/nochange.cpp | 37 --------- 13/open/gold/yinyang.cpp | 97 ------------------------ 14.5/dec/gold/guard.cpp | 17 +++++ 14.5/open/gold/googol.py | 12 +++ 14/dec/gold/guard.cpp | 17 ----- 15.5/dec/plat/maxflow.cpp | 59 +++++++++++++++ 15.5/open/plat/landscape.cpp | 70 +++++++++++++++++ 15/dec/plat/maxflow.cpp | 59 --------------- 15/open/gold/googol.py | 12 --- 16.5/dec/plat/triangles.cpp | 113 ++++++++++++++++++++++++++++ 16.5/feb/plat/friendcross.cpp | 68 +++++++++++++++++ 16.5/feb/plat/mincross.cpp | 57 ++++++++++++++ 16.5/feb/plat/nocross.cpp | 57 ++++++++++++++ 16.5/open/plat/cowbasic.cpp | 103 +++++++++++++++++++++++++ 16/dec/plat/triangles.cpp | 113 ---------------------------- 16/open/plat/landscape.cpp | 70 ----------------- 17.5/feb/plat/gymnasts.cpp | 97 ++++++++++++++++++++++++ 17.5/feb/plat/newbarn.cpp | 78 +++++++++++++++++++ 17.5/feb/plat/newbarn_naive.cpp | 72 ++++++++++++++++++ 17.5/open/plat/sort.cpp | 161 ++++++++++++++++++++++++++++++++++++++++ 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.5/dec/plat/balance.cpp | 62 ++++++++++++++++ 18.5/dec/plat/itout.cpp | 99 ++++++++++++++++++++++++ 18.5/open/plat/boxes.cpp | 75 +++++++++++++++++++ 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.5/dec/gold/cowmbat.cpp | 48 ++++++++++++ 19.5/dec/gold/milkvisits.cpp | 70 +++++++++++++++++ 19.5/dec/gold/pump.cpp | 46 ++++++++++++ 19.5/dec/plat/snowcow.cpp | 127 +++++++++++++++++++++++++++++++ 19.5/feb/gold/deleg.cpp | 66 ++++++++++++++++ 19.5/feb/gold/timeline.cpp | 37 +++++++++ 19.5/feb/plat/help.cpp | 116 +++++++++++++++++++++++++++++ 19.5/jan/gold/boards.cpp | 50 +++++++++++++ 19.5/jan/gold/threesum.cpp | 40 ++++++++++ 19.5/jan/gold/time.cpp | 35 +++++++++ 19.5/jan/plat/nondec.cpp | 108 +++++++++++++++++++++++++++ 19.5/open/gold/exercise.cpp | 35 +++++++++ 19.5/open/gold/fcolor.cpp | 38 ++++++++++ 19.5/open/gold/haircut.cpp | 59 +++++++++++++++ 19.5/open/plat/sprinklers2.cpp | 68 +++++++++++++++++ 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.5/dec/plat/sleeping.cpp | 47 ++++++++++++ 20.5/dec/plat/spaceship.cpp | 49 ++++++++++++ 20.5/feb/plat/minimizing.cpp | 78 +++++++++++++++++++ 20.5/feb/plat/notime.cpp | 64 ++++++++++++++++ 20.5/open/balanced.cpp | 118 +++++++++++++++++++++++++++++ 20.5/open/balanced_slow.cpp | 73 ++++++++++++++++++ 20.5/open/ucfj.cpp | 71 ++++++++++++++++++ 20/dec/plat/sleeping.cpp | 47 ------------ 20/dec/plat/spaceship.cpp | 49 ------------ 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 ----------------- 21.5/dec/hilo.cpp | 35 +++++++++ 21.5/dec/tickets.cpp | 79 ++++++++++++++++++++ 21.5/feb/plat/sleeping.cpp | 78 +++++++++++++++++++ 21/dec/hilo.cpp | 35 --------- 21/dec/tickets.cpp | 79 -------------------- 21/feb/plat/minimizing.cpp | 78 ------------------- 21/feb/plat/notime.cpp | 64 ---------------- 21/open/balanced.cpp | 118 ----------------------------- 21/open/balanced_slow.cpp | 73 ------------------ 21/open/ucfj.cpp | 71 ------------------ 22/feb/plat/sleeping.cpp | 78 ------------------- 7.5/nov/gold/telewire.cpp | 15 ++++ 98 files changed, 3145 insertions(+), 3145 deletions(-) delete mode 100644 07/nov/gold/telewire.cpp create mode 100644 11.5/dec/gold/photo.cpp create mode 100644 11.5/mar/gold/restack.cpp delete mode 100644 11/dec/gold/photo.cpp create mode 100644 12.5/feb/gold/route.cpp create mode 100644 12.5/nov/gold/bbreeds.cpp create mode 100644 12.5/nov/gold/btree.cpp create mode 100644 12.5/open/gold/yinyang.cpp delete mode 100644 12/mar/gold/restack.cpp delete mode 100644 12/nov/gold/bbreeds.cpp delete mode 100644 12/nov/gold/btree.cpp create mode 100644 13.5/nov/gold/nochange.cpp delete mode 100644 13/feb/gold/route.cpp delete mode 100644 13/nov/gold/nochange.cpp delete mode 100644 13/open/gold/yinyang.cpp create mode 100644 14.5/dec/gold/guard.cpp create mode 100644 14.5/open/gold/googol.py delete mode 100644 14/dec/gold/guard.cpp create mode 100644 15.5/dec/plat/maxflow.cpp create mode 100644 15.5/open/plat/landscape.cpp delete mode 100644 15/dec/plat/maxflow.cpp delete mode 100644 15/open/gold/googol.py create mode 100644 16.5/dec/plat/triangles.cpp create mode 100644 16.5/feb/plat/friendcross.cpp create mode 100644 16.5/feb/plat/mincross.cpp create mode 100644 16.5/feb/plat/nocross.cpp create mode 100644 16.5/open/plat/cowbasic.cpp delete mode 100644 16/dec/plat/triangles.cpp delete mode 100644 16/open/plat/landscape.cpp create mode 100644 17.5/feb/plat/gymnasts.cpp create mode 100644 17.5/feb/plat/newbarn.cpp create mode 100644 17.5/feb/plat/newbarn_naive.cpp create mode 100644 17.5/open/plat/sort.cpp delete mode 100644 17/feb/plat/friendcross.cpp delete mode 100644 17/feb/plat/mincross.cpp delete mode 100644 17/feb/plat/nocross.cpp delete mode 100644 17/open/plat/cowbasic.cpp create mode 100644 18.5/dec/plat/balance.cpp create mode 100644 18.5/dec/plat/itout.cpp create mode 100644 18.5/open/plat/boxes.cpp delete mode 100644 18/dec/plat/balance.cpp delete mode 100644 18/dec/plat/itout.cpp delete mode 100644 18/feb/plat/gymnasts.cpp delete mode 100644 18/feb/plat/newbarn.cpp delete mode 100644 18/feb/plat/newbarn_naive.cpp delete mode 100644 18/open/plat/sort.cpp create mode 100644 19.5/dec/gold/cowmbat.cpp create mode 100644 19.5/dec/gold/milkvisits.cpp create mode 100644 19.5/dec/gold/pump.cpp create mode 100644 19.5/dec/plat/snowcow.cpp create mode 100644 19.5/feb/gold/deleg.cpp create mode 100644 19.5/feb/gold/timeline.cpp create mode 100644 19.5/feb/plat/help.cpp create mode 100644 19.5/jan/gold/boards.cpp create mode 100644 19.5/jan/gold/threesum.cpp create mode 100644 19.5/jan/gold/time.cpp create mode 100644 19.5/jan/plat/nondec.cpp create mode 100644 19.5/open/gold/exercise.cpp create mode 100644 19.5/open/gold/fcolor.cpp create mode 100644 19.5/open/gold/haircut.cpp create mode 100644 19.5/open/plat/sprinklers2.cpp delete mode 100644 19/dec/gold/cowmbat.cpp delete mode 100644 19/dec/gold/milkvisits.cpp delete mode 100644 19/dec/gold/pump.cpp delete mode 100644 19/dec/plat/snowcow.cpp delete mode 100644 19/open/plat/boxes.cpp create mode 100644 20.5/dec/plat/sleeping.cpp create mode 100644 20.5/dec/plat/spaceship.cpp create mode 100644 20.5/feb/plat/minimizing.cpp create mode 100644 20.5/feb/plat/notime.cpp create mode 100644 20.5/open/balanced.cpp create mode 100644 20.5/open/balanced_slow.cpp create mode 100644 20.5/open/ucfj.cpp delete mode 100644 20/dec/plat/sleeping.cpp delete mode 100644 20/dec/plat/spaceship.cpp delete mode 100644 20/feb/gold/deleg.cpp delete mode 100644 20/feb/gold/timeline.cpp delete mode 100644 20/feb/plat/help.cpp delete mode 100644 20/jan/gold/boards.cpp delete mode 100644 20/jan/gold/threesum.cpp delete mode 100644 20/jan/gold/time.cpp delete mode 100644 20/jan/plat/nondec.cpp delete mode 100644 20/open/gold/exercise.cpp delete mode 100644 20/open/gold/fcolor.cpp delete mode 100644 20/open/gold/haircut.cpp delete mode 100644 20/open/plat/sprinklers2.cpp create mode 100644 21.5/dec/hilo.cpp create mode 100644 21.5/dec/tickets.cpp create mode 100644 21.5/feb/plat/sleeping.cpp delete mode 100644 21/dec/hilo.cpp delete mode 100644 21/dec/tickets.cpp delete mode 100644 21/feb/plat/minimizing.cpp delete mode 100644 21/feb/plat/notime.cpp delete mode 100644 21/open/balanced.cpp delete mode 100644 21/open/balanced_slow.cpp delete mode 100644 21/open/ucfj.cpp delete mode 100644 22/feb/plat/sleeping.cpp create mode 100644 7.5/nov/gold/telewire.cpp diff --git a/07/nov/gold/telewire.cpp b/07/nov/gold/telewire.cpp deleted file mode 100644 index e68ae69..0000000 --- a/07/nov/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/11.5/dec/gold/photo.cpp b/11.5/dec/gold/photo.cpp new file mode 100644 index 0000000..3492b8c --- /dev/null +++ b/11.5/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/11.5/mar/gold/restack.cpp b/11.5/mar/gold/restack.cpp new file mode 100644 index 0000000..49b325d --- /dev/null +++ b/11.5/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/11/dec/gold/photo.cpp b/11/dec/gold/photo.cpp deleted file mode 100644 index 3492b8c..0000000 --- a/11/dec/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/12.5/feb/gold/route.cpp b/12.5/feb/gold/route.cpp new file mode 100644 index 0000000..aab04ed --- /dev/null +++ b/12.5/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/12.5/nov/gold/bbreeds.cpp b/12.5/nov/gold/bbreeds.cpp new file mode 100644 index 0000000..9d7a745 --- /dev/null +++ b/12.5/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.5/nov/gold/btree.cpp b/12.5/nov/gold/btree.cpp new file mode 100644 index 0000000..16462ab --- /dev/null +++ b/12.5/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/12.5/open/gold/yinyang.cpp b/12.5/open/gold/yinyang.cpp new file mode 100644 index 0000000..9ce4aec --- /dev/null +++ b/12.5/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/12/mar/gold/restack.cpp b/12/mar/gold/restack.cpp deleted file mode 100644 index 49b325d..0000000 --- a/12/mar/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/12/nov/gold/bbreeds.cpp b/12/nov/gold/bbreeds.cpp deleted file mode 100644 index 9d7a745..0000000 --- a/12/nov/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/12/nov/gold/btree.cpp b/12/nov/gold/btree.cpp deleted file mode 100644 index 16462ab..0000000 --- a/12/nov/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/13.5/nov/gold/nochange.cpp b/13.5/nov/gold/nochange.cpp new file mode 100644 index 0000000..ad34b80 --- /dev/null +++ b/13.5/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/feb/gold/route.cpp b/13/feb/gold/route.cpp deleted file mode 100644 index aab04ed..0000000 --- a/13/feb/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/13/nov/gold/nochange.cpp b/13/nov/gold/nochange.cpp deleted file mode 100644 index ad34b80..0000000 --- a/13/nov/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/13/open/gold/yinyang.cpp b/13/open/gold/yinyang.cpp deleted file mode 100644 index 9ce4aec..0000000 --- a/13/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/14.5/dec/gold/guard.cpp b/14.5/dec/gold/guard.cpp new file mode 100644 index 0000000..f1c83c8 --- /dev/null +++ b/14.5/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/14.5/open/gold/googol.py b/14.5/open/gold/googol.py new file mode 100644 index 0000000..5eeb3be --- /dev/null +++ b/14.5/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/14/dec/gold/guard.cpp b/14/dec/gold/guard.cpp deleted file mode 100644 index f1c83c8..0000000 --- a/14/dec/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/15.5/dec/plat/maxflow.cpp b/15.5/dec/plat/maxflow.cpp new file mode 100644 index 0000000..88f3cda --- /dev/null +++ b/15.5/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.5/open/plat/landscape.cpp b/15.5/open/plat/landscape.cpp new file mode 100644 index 0000000..46e8d8e --- /dev/null +++ b/15.5/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/15/dec/plat/maxflow.cpp b/15/dec/plat/maxflow.cpp deleted file mode 100644 index 88f3cda..0000000 --- a/15/dec/plat/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/15/open/gold/googol.py b/15/open/gold/googol.py deleted file mode 100644 index 5eeb3be..0000000 --- a/15/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/16.5/dec/plat/triangles.cpp b/16.5/dec/plat/triangles.cpp new file mode 100644 index 0000000..1a2fdd9 --- /dev/null +++ b/16.5/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.5/feb/plat/friendcross.cpp b/16.5/feb/plat/friendcross.cpp new file mode 100644 index 0000000..de7c198 --- /dev/null +++ b/16.5/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/16.5/feb/plat/mincross.cpp b/16.5/feb/plat/mincross.cpp new file mode 100644 index 0000000..a5befd0 --- /dev/null +++ b/16.5/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/16.5/feb/plat/nocross.cpp b/16.5/feb/plat/nocross.cpp new file mode 100644 index 0000000..5ce1b7c --- /dev/null +++ b/16.5/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/16.5/open/plat/cowbasic.cpp b/16.5/open/plat/cowbasic.cpp new file mode 100644 index 0000000..8ef44c9 --- /dev/null +++ b/16.5/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/16/dec/plat/triangles.cpp b/16/dec/plat/triangles.cpp deleted file mode 100644 index 1a2fdd9..0000000 --- a/16/dec/plat/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/16/open/plat/landscape.cpp b/16/open/plat/landscape.cpp deleted file mode 100644 index 46e8d8e..0000000 --- a/16/open/plat/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/17.5/feb/plat/gymnasts.cpp b/17.5/feb/plat/gymnasts.cpp new file mode 100644 index 0000000..8904cbf --- /dev/null +++ b/17.5/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/17.5/feb/plat/newbarn.cpp b/17.5/feb/plat/newbarn.cpp new file mode 100644 index 0000000..e702480 --- /dev/null +++ b/17.5/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/17.5/feb/plat/newbarn_naive.cpp b/17.5/feb/plat/newbarn_naive.cpp new file mode 100644 index 0000000..86a3cd5 --- /dev/null +++ b/17.5/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/17.5/open/plat/sort.cpp b/17.5/open/plat/sort.cpp new file mode 100644 index 0000000..8e7a49a --- /dev/null +++ b/17.5/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/17/feb/plat/friendcross.cpp b/17/feb/plat/friendcross.cpp deleted file mode 100644 index de7c198..0000000 --- a/17/feb/plat/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/17/feb/plat/mincross.cpp b/17/feb/plat/mincross.cpp deleted file mode 100644 index a5befd0..0000000 --- a/17/feb/plat/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/17/feb/plat/nocross.cpp b/17/feb/plat/nocross.cpp deleted file mode 100644 index 5ce1b7c..0000000 --- a/17/feb/plat/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/17/open/plat/cowbasic.cpp b/17/open/plat/cowbasic.cpp deleted file mode 100644 index 8ef44c9..0000000 --- a/17/open/plat/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/18.5/dec/plat/balance.cpp b/18.5/dec/plat/balance.cpp new file mode 100644 index 0000000..154adbe --- /dev/null +++ b/18.5/dec/plat/balance.cpp @@ -0,0 +1,62 @@ +#define _CRT_SECURE_NO_WARNINGS +#include +#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.5/dec/plat/itout.cpp b/18.5/dec/plat/itout.cpp new file mode 100644 index 0000000..ce77c87 --- /dev/null +++ b/18.5/dec/plat/itout.cpp @@ -0,0 +1,99 @@ +#include +#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.5/open/plat/boxes.cpp b/18.5/open/plat/boxes.cpp new file mode 100644 index 0000000..75695b9 --- /dev/null +++ b/18.5/open/plat/boxes.cpp @@ -0,0 +1,75 @@ +#include +#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/18/dec/plat/balance.cpp b/18/dec/plat/balance.cpp deleted file mode 100644 index 154adbe..0000000 --- a/18/dec/plat/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/18/dec/plat/itout.cpp b/18/dec/plat/itout.cpp deleted file mode 100644 index ce77c87..0000000 --- a/18/dec/plat/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/18/feb/plat/gymnasts.cpp b/18/feb/plat/gymnasts.cpp deleted file mode 100644 index 8904cbf..0000000 --- a/18/feb/plat/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/18/feb/plat/newbarn.cpp b/18/feb/plat/newbarn.cpp deleted file mode 100644 index e702480..0000000 --- a/18/feb/plat/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/18/feb/plat/newbarn_naive.cpp b/18/feb/plat/newbarn_naive.cpp deleted file mode 100644 index 86a3cd5..0000000 --- a/18/feb/plat/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/18/open/plat/sort.cpp b/18/open/plat/sort.cpp deleted file mode 100644 index 8e7a49a..0000000 --- a/18/open/plat/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/19.5/dec/gold/cowmbat.cpp b/19.5/dec/gold/cowmbat.cpp new file mode 100644 index 0000000..e224936 --- /dev/null +++ b/19.5/dec/gold/cowmbat.cpp @@ -0,0 +1,48 @@ +#include +using namespace std; +typedef long long ll; + +ll a[30][30], cost[100001][30] = { 0 }, DP[100001][30]; + +int main() { + ifstream cin("cowmbat.in"); + ofstream cout("cowmbat.out"); + + int N, M, K; + string S; + cin >> N >> M >> K >> S; + for (int i = 0; i <= 26; ++i) { + for (int j = 0; j <= 26; ++j) a[i][j] = 1e9; + } + for (int i = 0; i < M; ++i) { + for (int j = 0; j < M; ++j) cin >> a[i][j]; + } + + for (int k = 0; k < M; ++k) { + for (int i = 0; i < M; ++i) { + for (int j = 0; j < M; ++j) a[i][j] = min(a[i][k] + a[k][j], a[i][j]); + } + } + + for (int i = 0; i < K; ++i) { + for (int j = 0; j <= 26; ++j) cost[0][j] += a[S[i] - 'a'][j]; + } + for (int i = 0; i < N - K; ++i) { + for (int j = 0; j <= 26; ++j) { + cost[i + 1][j] = a[S[i + K] - 'a'][j] - a[S[i] - 'a'][j] + cost[i][j]; + } + } + + for (int i = 0; i <= N; ++i) { + for (int j = 0; j <= 26; ++j) DP[i][j] = 1e9; + } + DP[0][26] = 0; + for (int i = 0; i < N; ++i) { + for (int j = 0; j <= 26; ++j) DP[i + 1][j] = min(a[S[i] - 'a'][j] + DP[i][j], DP[i + 1][j]); + int best = *min_element(DP[i], DP[i] + 27); + if (i + K <= N) { + for (int j = 0; j <= 26; ++j) DP[i + K][j] = min(best + cost[i][j], DP[i + K][j]); + } + } + cout << *min_element(DP[N], DP[N] + 27); +} diff --git a/19.5/dec/gold/milkvisits.cpp b/19.5/dec/gold/milkvisits.cpp new file mode 100644 index 0000000..d02c1bc --- /dev/null +++ b/19.5/dec/gold/milkvisits.cpp @@ -0,0 +1,70 @@ +#include +#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.5/dec/gold/pump.cpp b/19.5/dec/gold/pump.cpp new file mode 100644 index 0000000..20beb76 --- /dev/null +++ b/19.5/dec/gold/pump.cpp @@ -0,0 +1,46 @@ +#include +#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.5/dec/plat/snowcow.cpp b/19.5/dec/plat/snowcow.cpp new file mode 100644 index 0000000..b4df8bd --- /dev/null +++ b/19.5/dec/plat/snowcow.cpp @@ -0,0 +1,127 @@ +#include +#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.5/feb/gold/deleg.cpp b/19.5/feb/gold/deleg.cpp new file mode 100644 index 0000000..ee9144f --- /dev/null +++ b/19.5/feb/gold/deleg.cpp @@ -0,0 +1,66 @@ +#include +#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/19.5/feb/gold/timeline.cpp b/19.5/feb/gold/timeline.cpp new file mode 100644 index 0000000..6a9c217 --- /dev/null +++ b/19.5/feb/gold/timeline.cpp @@ -0,0 +1,37 @@ +#include +#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/19.5/feb/plat/help.cpp b/19.5/feb/plat/help.cpp new file mode 100644 index 0000000..e6ae965 --- /dev/null +++ b/19.5/feb/plat/help.cpp @@ -0,0 +1,116 @@ +#include +#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/19.5/jan/gold/boards.cpp b/19.5/jan/gold/boards.cpp new file mode 100644 index 0000000..812c959 --- /dev/null +++ b/19.5/jan/gold/boards.cpp @@ -0,0 +1,50 @@ +#include +#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/19.5/jan/gold/threesum.cpp b/19.5/jan/gold/threesum.cpp new file mode 100644 index 0000000..21e266c --- /dev/null +++ b/19.5/jan/gold/threesum.cpp @@ -0,0 +1,40 @@ +#include +#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/19.5/jan/gold/time.cpp b/19.5/jan/gold/time.cpp new file mode 100644 index 0000000..fd3b8cf --- /dev/null +++ b/19.5/jan/gold/time.cpp @@ -0,0 +1,35 @@ +#include +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/19.5/jan/plat/nondec.cpp b/19.5/jan/plat/nondec.cpp new file mode 100644 index 0000000..2084a05 --- /dev/null +++ b/19.5/jan/plat/nondec.cpp @@ -0,0 +1,108 @@ +#include +#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/19.5/open/gold/exercise.cpp b/19.5/open/gold/exercise.cpp new file mode 100644 index 0000000..7e8ba80 --- /dev/null +++ b/19.5/open/gold/exercise.cpp @@ -0,0 +1,35 @@ +#include +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/19.5/open/gold/fcolor.cpp b/19.5/open/gold/fcolor.cpp new file mode 100644 index 0000000..5a3879d --- /dev/null +++ b/19.5/open/gold/fcolor.cpp @@ -0,0 +1,38 @@ +#include +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/19.5/open/gold/haircut.cpp b/19.5/open/gold/haircut.cpp new file mode 100644 index 0000000..0e93c45 --- /dev/null +++ b/19.5/open/gold/haircut.cpp @@ -0,0 +1,59 @@ +#include +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/19.5/open/plat/sprinklers2.cpp b/19.5/open/plat/sprinklers2.cpp new file mode 100644 index 0000000..fd2fe5a --- /dev/null +++ b/19.5/open/plat/sprinklers2.cpp @@ -0,0 +1,68 @@ +#include +#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/19/dec/gold/cowmbat.cpp b/19/dec/gold/cowmbat.cpp deleted file mode 100644 index e224936..0000000 --- a/19/dec/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/19/dec/gold/milkvisits.cpp b/19/dec/gold/milkvisits.cpp deleted file mode 100644 index d02c1bc..0000000 --- a/19/dec/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/19/dec/gold/pump.cpp b/19/dec/gold/pump.cpp deleted file mode 100644 index 20beb76..0000000 --- a/19/dec/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/19/dec/plat/snowcow.cpp b/19/dec/plat/snowcow.cpp deleted file mode 100644 index b4df8bd..0000000 --- a/19/dec/plat/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/19/open/plat/boxes.cpp b/19/open/plat/boxes.cpp deleted file mode 100644 index 75695b9..0000000 --- a/19/open/plat/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/20.5/dec/plat/sleeping.cpp b/20.5/dec/plat/sleeping.cpp new file mode 100644 index 0000000..a7ad9f5 --- /dev/null +++ b/20.5/dec/plat/sleeping.cpp @@ -0,0 +1,47 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +const int MX = 3005, MOD = 1e9+7; + + +ll s[MX], t[MX], DP[2][MX][2]; + + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + ios_base::sync_with_stdio(0), cin.tie(0); + + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> s[i]; + for (int i = 0; i < N; ++i) cin >> t[i]; + + vector vc; + for (int i = 0; i < N; ++i) vc.emplace_back(s[i], 0); + for (int i = 0; i < N; ++i) vc.emplace_back(t[i], 1); + sort(begin(vc), end(vc)); + + DP[0][0][0] = 1; + for (int i = 0; i < 2*N; ++i) { + if (vc[i].s == 0) { + for (int j = 0; j <= N; ++j) { + (DP[1][j][1] += DP[0][j][0]) %= MOD; + (DP[1][j+1][0] += DP[0][j][0]) %= MOD; + (DP[1][j][1] += DP[0][j][1]) %= MOD; + (DP[1][j+1][1] += DP[0][j][1]) %= MOD; + } + } + else { + for (int j = 0; j <= N; ++j) { + (DP[1][j][0] += DP[0][j][0]) %= MOD; + if (j) (DP[1][j-1][0] += j*DP[0][j][0]) %= MOD; + if (j) (DP[1][j-1][1] += j*DP[0][j][1]) %= MOD; + } + } + memcpy(DP[0], DP[1], sizeof DP[1]); + memset(DP[1], 0, sizeof DP[1]); + } + cout << (DP[0][0][0]+DP[0][0][1])%MOD; +} diff --git a/20.5/dec/plat/spaceship.cpp b/20.5/dec/plat/spaceship.cpp new file mode 100644 index 0000000..d8d7849 --- /dev/null +++ b/20.5/dec/plat/spaceship.cpp @@ -0,0 +1,49 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 65, MOD = 1e9+7; + +ll bs[MX], s[MX], bt[MX], t[MX], L[2*MX], R[2*MX], G[MX][MX], DP[MX][2*MX][2*MX]; + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + ios_base::sync_with_stdio(0), cin.tie(0); + + int N, K, Q; cin >> N >> K >> Q; + for (int i = 0; i < N; ++i) { + string s; cin >> s; + for (int j = 0; j < N; ++j) G[i][j] = s[j] == '1'; + } + for (int i = 0; i < Q; ++i) + cin >> bs[i] >> s[i] >> bt[i] >> t[i], --bs[i], --s[i], --bt[i], --t[i]; + + for (int i = 0; i < K; ++i) { + for (int j = 0; j < N; ++j) { + for (int k = 0; k < N+Q; ++k) L[k] = k == j; + for (int k = 0; k < Q; ++k) + if (i == bs[k] && j == s[k]) L[N+k] = 1; + + for (int k = 0; k < N+Q; ++k) + for (int l = 0; l < N; ++l) + if (i && G[l][j]) (L[k] += DP[i-1][k][l]) %= MOD; + + for (int k = 0; k < N+Q; ++k) R[k] = k == j; + for (int k = 0; k < Q; ++k) + if (i == bt[k] && j == t[k]) R[N+k] = 1; + + for (int k = 0; k < N+Q; ++k) + for (int l = 0; l < N; ++l) + if (i && G[j][l]) (R[k] += DP[i-1][l][k]) %= MOD; + + for (int k = 0; k < N+Q; ++k) + for (int l = 0; l < N+Q; ++l) + (DP[i][k][l] += L[k]*R[l]) %= MOD; + } + memcpy(DP[i+1], DP[i], sizeof DP[i]); + } + + for (int i = 0; i < Q; ++i) cout << DP[K][N+i][N+i] << '\n'; +} diff --git a/20.5/feb/plat/minimizing.cpp b/20.5/feb/plat/minimizing.cpp new file mode 100644 index 0000000..9d5bf95 --- /dev/null +++ b/20.5/feb/plat/minimizing.cpp @@ -0,0 +1,78 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 1e5+5; + +int ans, D[2*MX]; +vector G[MX], H[2*MX]; + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + cin.tie(0)->sync_with_stdio(0); + + int T; cin >> T; + while (T--) { + int N, M; cin >> N >> M; + for (int u = 1; u <= N; ++u) G[u].clear(); + for (int u = 1; u <= 2*N; ++u) H[u].clear(); + for (int i = 0; i < M; ++i) { + int x, y; cin >> x >> y; + G[x].push_back(y), G[y].push_back(x); + H[x].push_back(y+N), H[y+N].push_back(x); + H[y].push_back(x+N), H[x+N].push_back(y); + } + + for (int u = 1; u <= 2*N; ++u) D[u] = 1e9; + queue q; + D[1] = 0, q.push(1); + while (q.size()) { + int u = q.front(); q.pop(); + for (int v : H[u]) if (D[v] == 1e9) + D[v] = D[u]+1, q.push(v); + } + + if (*max_element(D+1, D+2*N+1) == 1e9) { + cout << N-1 << '\n'; + continue; + } + + /*vector C; + C.emplace_back(0, 0); + for (int u = 1; u <= N; ++u) { + C.emplace_back(D[u], D[u+N]); + }*/ + + ans = 0; + map f; + map> b; + for (int u = 1; u <= N; ++u) { + ii p(min(D[u], D[u+N]), max(D[u], D[u+N])); + ++f[p], b[p].push_back(u); + } + map ea; + for (auto [p, c] : f) { + int pr = ea[ii(p.f-1, p.s+1)]; + if (p.f+1 == p.s) { + if (p.f == 0) ans += (c+1)/2; + else if (f[ii(p.f-1, p.s-1)]) ans += max((c-pr)+(pr+1)/2, (c+1)/2); + else { + if (pr < c) ans += c-pr; + ans += (c+1)/2; + } + } + else { + ans += c; + if (p.f == 0) ea[p] = c; + else if (f[ii(p.f-1, p.s-1)]) ea[p] += min(c, pr); + else { + if (pr < c) ans += c-pr; + ea[p] = c; + } + } + } + cout << ans << '\n'; + } +} diff --git a/20.5/feb/plat/notime.cpp b/20.5/feb/plat/notime.cpp new file mode 100644 index 0000000..48794bf --- /dev/null +++ b/20.5/feb/plat/notime.cpp @@ -0,0 +1,64 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 2e5+5, B = 300; + +int C[MX], L[MX], R[MX], ST[20][MX], ans[MX]; +pair P[MX]; + +inline int query(int i, int j) { + if (i > j) return MX; + int k = 31-__builtin_clz(j-i+1); + return min(ST[k][i], ST[k][j-(1<sync_with_stdio(0); + + int N, Q; cin >> N >> Q; + for (int i = 0; i < N; ++i) cin >> C[i]; + for (int i = 0; i < Q; ++i) { + cin >> P[i].f.f >> P[i].f.s; + --P[i].f.f, --P[i].f.s, P[i].s = i; + } + + vector tmp(N+1, -1); + for (int i = 0; i < N; ++i) L[i] = tmp[C[i]], tmp[C[i]] = i; + fill(begin(tmp), end(tmp), -1); + for (int i = N-1; i >= 0; --i) R[i] = tmp[C[i]], tmp[C[i]] = i; + + memset(ST, '?', sizeof ST); + for (int i = 0; i < N; ++i) ST[0][i] = C[i]; + for (int i = 0; i < 18; ++i) + for (int j = 0; j+(1<<(i+1)) < N; ++j) ST[i+1][j] = min(ST[i][j], ST[i][j+(1< b.f.s : a.f.s < b.f.s) : a.f.f/B < b.f.f/B; + }); + + int l = 0, r = -1, cur = 0; + for (int i = 0; i < Q; ++i) { + while (l > P[i].f.f) { + --l; + if (R[l] == -1 || R[l] > r || query(l+1, R[l]-1) < C[l]) ++cur; + } + while (r < P[i].f.s) { + ++r; + if (L[r] == -1 || L[r] < l || query(L[r]+1, r-1) < C[r]) ++cur; + } + while (l < P[i].f.f) { + if (R[l] == -1 || R[l] > r || query(l+1, R[l]-1) < C[l]) --cur; + ++l; + } + while (r > P[i].f.s) { + if (L[r] == -1 || L[r] < l || query(L[r]+1, r-1) < C[r]) --cur; + --r; + } + ans[P[i].s] = cur; + } + for (int i = 0; i < Q; ++i) cout << ans[i] << '\n'; +} diff --git a/20.5/open/balanced.cpp b/20.5/open/balanced.cpp new file mode 100644 index 0000000..02404a3 --- /dev/null +++ b/20.5/open/balanced.cpp @@ -0,0 +1,118 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 155, MOD = 1e9+7; + +inline void add(int & x, int y) { x += y; if (x > MOD) x -= MOD; } + +string S[MX]; + +struct fenwick_tree_2d { + int FT[MX][MX]; + fenwick_tree_2d() { memset(FT, 0, sizeof FT); } + inline void update(int x, int y, int v) { + for (int i = x+1; i < MX; i += i&-i) + for (int j = y+1; j < MX; j += j&-j) add(FT[i][j], v); + } + inline int query(int x, int y) { + int ret = 0; + for (int i = x+1; i > 0; i -= i&-i) + for (int j = y+1; j > 0; j -= j&-j) add(ret, FT[i][j]); + return ret; + } + inline int query(int xl, int xr, int yl, int yr) { + int ret = query(xr, yr); + add(ret, MOD-query(xl-1, yr)); + add(ret, MOD-query(xr, yl-1)); + add(ret, query(xl-1, yl-1)); + return ret; + } +} DP[MX][4]; + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + cin.tie(0)->sync_with_stdio(0); + + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> S[i]; + + int ans = 0; + for (int i = 0; i < N; ++i) { + for (int a = 0; a < N; ++a) { + for (int b = a; b < N; ++b) { + if (S[i][b] != 'G') break; + + int sum = 1; + + int d0bb = DP[i][0].query(b,b); + int d0a1b = DP[i][0].query(a-1,b); + int d0ba1 = DP[i][0].query(b,a-1); + int d0a1a1 = DP[i][0].query(a-1,a-1); + // DP[i][0] query(b,b)-query(a-1,b)-query(b,a-1)+query(a-1,a-1); + // add(sum, DP[i][0].query(a, b, a, b)); + add(sum, d0bb), add(sum, MOD-d0a1b), add(sum, MOD-d0ba1), add(sum, d0a1a1); + DP[i+1][0].update(a, b, sum); + add(ans, sum); + + int d1bn1 = DP[i][1].query(b, N-1); + int d1a1n1 = DP[i][1].query(a-1, N-1); + int d1bb1 = DP[i][1].query(b,b-1); + int d1a1b1 = DP[i][1].query(a-1,b-1); + int d0bn1 = DP[i][0].query(b,N-1); + int d0a1n1 = DP[i][0].query(a-1,N-1); + // DP[i][1] query(b, N-1)-query(a-1,N-1)-query(b,b-1)+query(a-1, b-1) + // DP[i][0] query(b, N-1)-query(a-1, N-1)-query(b,b)+query(a-1, b) + // sum = DP[i][1].query(a, b, b, N-1); + sum = 0; add(sum, d1bn1), add(sum, MOD-d1a1n1), add(sum, MOD-d1bb1), add(sum, d1a1b1); + // add(sum, DP[i][0].query(a, b, b+1, N-1)); + add(sum, d0bn1), add(sum, MOD-d0a1n1), add(sum, MOD-d0bb), add(sum, d0a1b); + DP[i+1][1].update(a, b, sum); + add(ans, sum); + + int d2ab = DP[i][2].query(a, b); + //int d21b = 0; //DP[i][2].query(-1, b); + int d2aa1 = DP[i][2].query(a, a-1); + //int d21a1 = 0; //DP[i][2].query(-1, a-1); + //int d01b = 0; //DP[i][0].query(-1, b); + //int d01a1 = 0; //DP[i][0].query(-1, a-1); + // DP[i][2] query(a,b)-query(-1,b)-query(a, a-1)+query(-1, a-1) + // DP[i][0] query(a-1, b)-query(-1,b)-query(a-1,a-1)+query(-1,a-1) + // sum = DP[i][2].query(0, a, a, b); + sum = 0; add(sum, d2ab); //add(sum, MOD-d21b), + add(sum, MOD-d2aa1);//, add(sum, d21a1); + // add(sum, DP[i][0].query(0, a-1, a, b)); + add(sum, d0a1b);//, add(sum, MOD-d01b), + add(sum, MOD-d0a1a1);//, add(sum, d01a1); + DP[i+1][2].update(a, b, sum); + add(ans, sum); + + // int d01n1 = 0;//DP[i][0].query(-1,N-1); + // int d11n1 = 0;//DP[i][1].query(-1, N-1); + // int d11b1 = 0;//DP[i][1].query(-1, b-1); + int d2an1 = DP[i][2].query(a, N-1); + // int d21n1 = 0;//DP[i][2].query(-1, N-1); + // DP[i][3] query(a, N-1)-query(-1,N-1)-query(a,b-1)+query(-1, b-1) + // DP[i][0] query(a-1, N-1)-query(-1,N-1)-query(a-1,b)+query(-1, b) + // DP[i][1] query(a-1, N-1)-query(-1,N-1)-query(a-1,b-1)+query(-1, b-1) + // DP[i][2] query(a, N-1)-query(-1,N-1)-query(a,b)+query(-1, b) + sum = DP[i][3].query(a, N-1); add(sum, MOD-DP[i][3].query(a,b-1)); + // add(sum, DP[i][0].query(0, a-1, b+1, N-1)); + add(sum, d0a1n1);//, add(sum, MOD-d01n1), + add(sum, MOD-d0a1b);//, add(sum, d01b); + // add(sum, DP[i][1].query(0, a-1, b, N-1)); + add(sum, d1a1n1);//, add(sum, MOD-d11n1), + add(sum, MOD-d1a1b1);//, add(sum, d11b1); + // add(sum, DP[i][2].query(0, a, b+1, N-1)); + add(sum, d2an1); + //add(sum, MOD-d21n1), + add(sum, MOD-d2ab);//, add(sum, d21b); + DP[i+1][3].update(a, b, sum); + add(ans, sum); + } + } + } + cout << ans%MOD; +} diff --git a/20.5/open/balanced_slow.cpp b/20.5/open/balanced_slow.cpp new file mode 100644 index 0000000..3f7c3e9 --- /dev/null +++ b/20.5/open/balanced_slow.cpp @@ -0,0 +1,73 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 155, MOD = 1e9+7; + +inline void add(int & x, int y) { x += y; if (x > MOD) x -= MOD; } + +string S[MX]; + +struct fenwick_tree_2d { + int FT[MX][MX]; + fenwick_tree_2d() { memset(FT, 0, sizeof FT); } + inline void update(int x, int y, int v) { + for (int i = x+1; i < MX; i += i&-i) + for (int j = y+1; j < MX; j += j&-j) add(FT[i][j], v); + } + inline int query(int x, int y) { + int ret = 0; + for (int i = x+1; i > 0; i -= i&-i) + for (int j = y+1; j > 0; j -= j&-j) add(ret, FT[i][j]); + return ret; + } + inline int query(int xl, int xr, int yl, int yr) { + int ret = query(xr, yr); + add(ret, MOD-query(xl-1, yr)); + add(ret, MOD-query(xr, yl-1)); + add(ret, query(xl-1, yl-1)); + return ret; + } +} DP[MX][4]; + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + cin.tie(0)->sync_with_stdio(0); + + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> S[i]; + + int ans = 0; + for (int i = 0; i < N; ++i) { + for (int a = 0; a < N; ++a) { + for (int b = a; b < N; ++b) { + if (S[i][b] != 'G') break; + + int sum = 1; + add(sum, DP[i][0].query(a, b, a, b)); + DP[i+1][0].update(a, b, sum); + add(ans, sum); + + sum = DP[i][1].query(a, b, b, N-1); + add(sum, DP[i][0].query(a, b, b+1, N-1)); + DP[i+1][1].update(a, b, sum); + add(ans, sum); + + sum = DP[i][2].query(0, a, a, b); + add(sum, DP[i][0].query(0, a-1, a, b)); + DP[i+1][2].update(a, b, sum); + add(ans, sum); + + sum = DP[i][3].query(0, a, b, N-1); + add(sum, DP[i][0].query(0, a-1, b+1, N-1)); + add(sum, DP[i][1].query(0, a-1, b, N-1)); + add(sum, DP[i][2].query(0, a, b+1, N-1)); + DP[i+1][3].update(a, b, sum); + add(ans, sum); + } + } + } + cout << ans%MOD; +} diff --git a/20.5/open/ucfj.cpp b/20.5/open/ucfj.cpp new file mode 100644 index 0000000..e7d7475 --- /dev/null +++ b/20.5/open/ucfj.cpp @@ -0,0 +1,71 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 2e5+5; + +int b[MX], l[MX], s[MX]; + +struct fenwick_tree { + int FT[MX]; + fenwick_tree() { memset(FT, 0, sizeof FT); } + inline void update(int x, int v) { if (++x) for (; x < MX; x += x&-x) FT[x] += v; } + inline int query(int x) { int ret = 0; if (++x) for (; x; x -= x&-x) ret += FT[x]; return ret; } + inline int query(int x, int y) { return query(y)-query(x-1); } +} range; + +struct seg_tree { + ll seg[4*MX], tmp[4*MX]; + seg_tree() { memset(seg, 0, sizeof seg), memset(tmp, 0, sizeof tmp); } + inline ll pull(ll a, ll b) { return a+b; } + inline void push(int l, int r, int n) { + if (tmp[n]) { + seg[n] += range.query(l, r) * 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 = MX-1, int n = 1) { + push(l, r, n); + if (l > r || l > b || r < a) return; + if (l >= a && r <= b) { tmp[n] += v, push(l, r, n); return; } + 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 = MX-1, int 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)); + } +} seg; + +int main() { + if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); + cin.tie(0)->sync_with_stdio(0); + + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> b[i]; + + memset(l, -1, sizeof l), memset(s, -1, sizeof s); + ll ans = 0; + for (int i = 0; i < N; ++i) { + if (l[b[i]] == -1) { + seg.update(0, i-2, 1); + } + else { + seg.update(s[b[i]]+1, l[b[i]]-1, -1); + seg.update(l[b[i]], l[b[i]], -seg.query(l[b[i]], l[b[i]])); + seg.update(l[b[i]]+1, i-2, 1); + range.update(l[b[i]], -1); + } + range.update(i, 1); + ans += seg.query(l[b[i]]+1, i-1); + s[b[i]] = l[b[i]], l[b[i]] = i; + } + cout << ans; +} diff --git a/20/dec/plat/sleeping.cpp b/20/dec/plat/sleeping.cpp deleted file mode 100644 index a7ad9f5..0000000 --- a/20/dec/plat/sleeping.cpp +++ /dev/null @@ -1,47 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -const int MX = 3005, MOD = 1e9+7; - - -ll s[MX], t[MX], DP[2][MX][2]; - - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - ios_base::sync_with_stdio(0), cin.tie(0); - - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> s[i]; - for (int i = 0; i < N; ++i) cin >> t[i]; - - vector vc; - for (int i = 0; i < N; ++i) vc.emplace_back(s[i], 0); - for (int i = 0; i < N; ++i) vc.emplace_back(t[i], 1); - sort(begin(vc), end(vc)); - - DP[0][0][0] = 1; - for (int i = 0; i < 2*N; ++i) { - if (vc[i].s == 0) { - for (int j = 0; j <= N; ++j) { - (DP[1][j][1] += DP[0][j][0]) %= MOD; - (DP[1][j+1][0] += DP[0][j][0]) %= MOD; - (DP[1][j][1] += DP[0][j][1]) %= MOD; - (DP[1][j+1][1] += DP[0][j][1]) %= MOD; - } - } - else { - for (int j = 0; j <= N; ++j) { - (DP[1][j][0] += DP[0][j][0]) %= MOD; - if (j) (DP[1][j-1][0] += j*DP[0][j][0]) %= MOD; - if (j) (DP[1][j-1][1] += j*DP[0][j][1]) %= MOD; - } - } - memcpy(DP[0], DP[1], sizeof DP[1]); - memset(DP[1], 0, sizeof DP[1]); - } - cout << (DP[0][0][0]+DP[0][0][1])%MOD; -} diff --git a/20/dec/plat/spaceship.cpp b/20/dec/plat/spaceship.cpp deleted file mode 100644 index d8d7849..0000000 --- a/20/dec/plat/spaceship.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 65, MOD = 1e9+7; - -ll bs[MX], s[MX], bt[MX], t[MX], L[2*MX], R[2*MX], G[MX][MX], DP[MX][2*MX][2*MX]; - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - ios_base::sync_with_stdio(0), cin.tie(0); - - int N, K, Q; cin >> N >> K >> Q; - for (int i = 0; i < N; ++i) { - string s; cin >> s; - for (int j = 0; j < N; ++j) G[i][j] = s[j] == '1'; - } - for (int i = 0; i < Q; ++i) - cin >> bs[i] >> s[i] >> bt[i] >> t[i], --bs[i], --s[i], --bt[i], --t[i]; - - for (int i = 0; i < K; ++i) { - for (int j = 0; j < N; ++j) { - for (int k = 0; k < N+Q; ++k) L[k] = k == j; - for (int k = 0; k < Q; ++k) - if (i == bs[k] && j == s[k]) L[N+k] = 1; - - for (int k = 0; k < N+Q; ++k) - for (int l = 0; l < N; ++l) - if (i && G[l][j]) (L[k] += DP[i-1][k][l]) %= MOD; - - for (int k = 0; k < N+Q; ++k) R[k] = k == j; - for (int k = 0; k < Q; ++k) - if (i == bt[k] && j == t[k]) R[N+k] = 1; - - for (int k = 0; k < N+Q; ++k) - for (int l = 0; l < N; ++l) - if (i && G[j][l]) (R[k] += DP[i-1][l][k]) %= MOD; - - for (int k = 0; k < N+Q; ++k) - for (int l = 0; l < N+Q; ++l) - (DP[i][k][l] += L[k]*R[l]) %= MOD; - } - memcpy(DP[i+1], DP[i], sizeof DP[i]); - } - - for (int i = 0; i < Q; ++i) cout << DP[K][N+i][N+i] << '\n'; -} diff --git a/20/feb/gold/deleg.cpp b/20/feb/gold/deleg.cpp deleted file mode 100644 index ee9144f..0000000 --- a/20/feb/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/20/feb/gold/timeline.cpp b/20/feb/gold/timeline.cpp deleted file mode 100644 index 6a9c217..0000000 --- a/20/feb/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/20/feb/plat/help.cpp b/20/feb/plat/help.cpp deleted file mode 100644 index e6ae965..0000000 --- a/20/feb/plat/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/20/jan/gold/boards.cpp b/20/jan/gold/boards.cpp deleted file mode 100644 index 812c959..0000000 --- a/20/jan/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/20/jan/gold/threesum.cpp b/20/jan/gold/threesum.cpp deleted file mode 100644 index 21e266c..0000000 --- a/20/jan/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/20/jan/gold/time.cpp b/20/jan/gold/time.cpp deleted file mode 100644 index fd3b8cf..0000000 --- a/20/jan/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/20/jan/plat/nondec.cpp b/20/jan/plat/nondec.cpp deleted file mode 100644 index 2084a05..0000000 --- a/20/jan/plat/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/20/open/gold/exercise.cpp b/20/open/gold/exercise.cpp deleted file mode 100644 index 7e8ba80..0000000 --- a/20/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/20/open/gold/fcolor.cpp b/20/open/gold/fcolor.cpp deleted file mode 100644 index 5a3879d..0000000 --- a/20/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/20/open/gold/haircut.cpp b/20/open/gold/haircut.cpp deleted file mode 100644 index 0e93c45..0000000 --- a/20/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/20/open/plat/sprinklers2.cpp b/20/open/plat/sprinklers2.cpp deleted file mode 100644 index fd2fe5a..0000000 --- a/20/open/plat/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'; -} diff --git a/21.5/dec/hilo.cpp b/21.5/dec/hilo.cpp new file mode 100644 index 0000000..250bf49 --- /dev/null +++ b/21.5/dec/hilo.cpp @@ -0,0 +1,35 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +constexpr int MX = 5005, MOD = 1e9+7; + +inline ll pw(ll base, ll exp) { + ll res = 1; + while (exp) { + if (exp & 1) (res *= base) %= MOD; + exp >>= 1, (base *= base) %= MOD; + } + return res; +} + +int inv[MX], pre[2][MX], DP[2][MX][MX]; + +int main() { + cin.tie(0)->sync_with_stdio(0); + int N, x; cin >> N >> x; + for (int i = 1; i <= N; ++i) inv[i] = pw(i, MOD-2); + for (int i = 0; i <= x; ++i) { + for (int j = 0; j <= N-x; ++j) { + DP[0][i][j] = (ll)(pre[0][i] + pre[1][j]) * inv[i + j] % MOD; + DP[1][i][j] = (ll)(pre[0][i] + pre[1][j] + i) * inv[i + j] % MOD; + (pre[0][i] += DP[1][i][j]) %= MOD; + (pre[1][j] += DP[0][i][j]) %= MOD; + } + } + ll ans = DP[0][x][N-x]; + for (int i = 1; i <= N; ++i) (ans *= i) %= MOD; + cout << ans; +} diff --git a/21.5/dec/tickets.cpp b/21.5/dec/tickets.cpp new file mode 100644 index 0000000..cd6e006 --- /dev/null +++ b/21.5/dec/tickets.cpp @@ -0,0 +1,79 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +using pl = pair; +constexpr int MX = 1e5+5; + +int N, K; + +struct ticket_t { + int c, p, a, b; +} T[MX]; + +struct seg_tree { + int seg[4*MX]; + inline int pull(const int & a, const int & b) { return max(a, b); } + void build(int l = 0, int r = MX-1, int n = 1) { + if (l == r) { seg[n] = T[l].b; return; } + int m = l+r>>1; + build(l, m, n<<1), build(m+1, r, n<<1|1); + seg[n] = pull(seg[n<<1], seg[n<<1|1]); + } + void remove(vector & vc, int x, int l = 0, int r = MX-1, int n = 1) { + if (l >= K || T[l].a > x || seg[n] < x) return; + if (l == r) { + seg[n] = -1, vc.push_back(l); + } + else { + int m = l+r>>1; + remove(vc, x, l, m, n<<1), remove(vc, x, m+1, r, n<<1|1); + seg[n] = pull(seg[n<<1], seg[n<<1|1]); + } + } +}; + +void dijkstra(vector & dist) { + priority_queue, greater<>> pq; + for (int i = N; i < N+K; ++i) + dist[T[i-N].c] = min(dist[i]+T[i-N].p, dist[T[i-N].c]); + for (int i = 0; i < N; ++i) if (dist[i] < 1e18) + pq.emplace(dist[i], i); + seg_tree seg; + seg.build(); + while (pq.size()) { + ll d = pq.top().f, u = pq.top().s; + pq.pop(); + if (d > dist[u]) continue; + vector vc; + seg.remove(vc, u); + for (int v : vc) { + if (dist[v+N] > d) { + dist[v+N] = d; + if (dist[T[v].c] > d+T[v].p) + dist[T[v].c] = d+T[v].p, + pq.emplace(dist[T[v].c], T[v].c); + } + } + } +} + +int main() { + cin.tie(0)->sync_with_stdio(0); + cin >> N >> K; + for (int i = 0; i < K; ++i) { + cin >> T[i].c >> T[i].p >> T[i].a >> T[i].b; + --T[i].c, --T[i].a, --T[i].b; + } + sort(T, T+K, [](auto & a, auto & b) { return a.a < b.a; }); + vector L(N+K, 1e18), R(N+K, 1e18), D(N+K); + L[0] = R[N-1] = 0; + dijkstra(L), dijkstra(R); + for (int i = 0; i < N+K; ++i) D[i] = L[i]+R[i]; + dijkstra(D); + for (int i = 0; i < N; ++i) + cout << (D[i] < 1e18 ? D[i] : -1) << '\n'; +} + diff --git a/21.5/feb/plat/sleeping.cpp b/21.5/feb/plat/sleeping.cpp new file mode 100644 index 0000000..4f1f5c8 --- /dev/null +++ b/21.5/feb/plat/sleeping.cpp @@ -0,0 +1,78 @@ +#include +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair; +const int MX = 1e5+5; + +ll A[MX], P[MX], q[MX]; +int f[103680]; +vector> pr; + +int num_factors() { + int ret = 1; + for (auto & p : pr) ret *= p.s+1; + return ret; +} + +int & freq(ll x) { + ll code = 0; + for (auto & p : pr) { + int cnt = 0; + while (x%p.f == 0) x/= p.f, ++cnt; + code = (p.s+1)*code + min(p.s, cnt); + } + return f[code]; +} + +int main() { + cin.tie(0)->sync_with_stdio(0); + int N; cin >> N; + for (int i = 0; i < N; ++i) cin >> A[i]; + partial_sum(A, A+N, P); + ll sum = P[N-1]; + for (int p = 2; p < 1e6; ++p) { + if (sum%p == 0) { + int cnt = 0; + while (sum%p == 0) sum /= p, ++cnt; + pr.emplace_back(p, cnt); + } + } + for (int i = 0; i < N; ++i) { + ll tmp = gcd(P[i], sum); + if (tmp != 1 && tmp != sum) { + if (tmp > sum/tmp) tmp = sum/tmp; + if (tmp*tmp == sum) pr.emplace_back(tmp, 2); + else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1); + sum = 1; + } + } + int Q; cin >> Q; + for (int i = 0; i < Q; ++i) { + cin >> q[i]; + ll tmp = q[i]; + if (sum%tmp == 0 && tmp != 1 && tmp != sum) { + if (tmp > sum/tmp) tmp = sum/tmp; + if (tmp*tmp == sum) pr.emplace_back(tmp, 2); + else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1); + sum = 1; + } + } + if (sum > 1) pr.emplace_back(sum, 1); + for (int i = 0; i < N; ++i) ++freq(P[i]); + int block = 1; + for (int i = pr.size()-1; i >= 0; --i) { + for (int code = num_factors()-1; code >= 0; --code) + if (code/block%(pr[i].s+1)!=0) f[code-block] += f[code]; + block *= pr[i].s+1; + } + for (int i = 0; i < Q; ++i) { + if (P[N-1]%q[i]) cout << -1 << '\n'; + else { + ll ans = N+P[N-1]/q[i]; + ans -= freq(q[i])*2; + cout << ans << '\n'; + } + } +} diff --git a/21/dec/hilo.cpp b/21/dec/hilo.cpp deleted file mode 100644 index 250bf49..0000000 --- a/21/dec/hilo.cpp +++ /dev/null @@ -1,35 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 5005, MOD = 1e9+7; - -inline ll pw(ll base, ll exp) { - ll res = 1; - while (exp) { - if (exp & 1) (res *= base) %= MOD; - exp >>= 1, (base *= base) %= MOD; - } - return res; -} - -int inv[MX], pre[2][MX], DP[2][MX][MX]; - -int main() { - cin.tie(0)->sync_with_stdio(0); - int N, x; cin >> N >> x; - for (int i = 1; i <= N; ++i) inv[i] = pw(i, MOD-2); - for (int i = 0; i <= x; ++i) { - for (int j = 0; j <= N-x; ++j) { - DP[0][i][j] = (ll)(pre[0][i] + pre[1][j]) * inv[i + j] % MOD; - DP[1][i][j] = (ll)(pre[0][i] + pre[1][j] + i) * inv[i + j] % MOD; - (pre[0][i] += DP[1][i][j]) %= MOD; - (pre[1][j] += DP[0][i][j]) %= MOD; - } - } - ll ans = DP[0][x][N-x]; - for (int i = 1; i <= N; ++i) (ans *= i) %= MOD; - cout << ans; -} diff --git a/21/dec/tickets.cpp b/21/dec/tickets.cpp deleted file mode 100644 index cd6e006..0000000 --- a/21/dec/tickets.cpp +++ /dev/null @@ -1,79 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -using pl = pair; -constexpr int MX = 1e5+5; - -int N, K; - -struct ticket_t { - int c, p, a, b; -} T[MX]; - -struct seg_tree { - int seg[4*MX]; - inline int pull(const int & a, const int & b) { return max(a, b); } - void build(int l = 0, int r = MX-1, int n = 1) { - if (l == r) { seg[n] = T[l].b; return; } - int m = l+r>>1; - build(l, m, n<<1), build(m+1, r, n<<1|1); - seg[n] = pull(seg[n<<1], seg[n<<1|1]); - } - void remove(vector & vc, int x, int l = 0, int r = MX-1, int n = 1) { - if (l >= K || T[l].a > x || seg[n] < x) return; - if (l == r) { - seg[n] = -1, vc.push_back(l); - } - else { - int m = l+r>>1; - remove(vc, x, l, m, n<<1), remove(vc, x, m+1, r, n<<1|1); - seg[n] = pull(seg[n<<1], seg[n<<1|1]); - } - } -}; - -void dijkstra(vector & dist) { - priority_queue, greater<>> pq; - for (int i = N; i < N+K; ++i) - dist[T[i-N].c] = min(dist[i]+T[i-N].p, dist[T[i-N].c]); - for (int i = 0; i < N; ++i) if (dist[i] < 1e18) - pq.emplace(dist[i], i); - seg_tree seg; - seg.build(); - while (pq.size()) { - ll d = pq.top().f, u = pq.top().s; - pq.pop(); - if (d > dist[u]) continue; - vector vc; - seg.remove(vc, u); - for (int v : vc) { - if (dist[v+N] > d) { - dist[v+N] = d; - if (dist[T[v].c] > d+T[v].p) - dist[T[v].c] = d+T[v].p, - pq.emplace(dist[T[v].c], T[v].c); - } - } - } -} - -int main() { - cin.tie(0)->sync_with_stdio(0); - cin >> N >> K; - for (int i = 0; i < K; ++i) { - cin >> T[i].c >> T[i].p >> T[i].a >> T[i].b; - --T[i].c, --T[i].a, --T[i].b; - } - sort(T, T+K, [](auto & a, auto & b) { return a.a < b.a; }); - vector L(N+K, 1e18), R(N+K, 1e18), D(N+K); - L[0] = R[N-1] = 0; - dijkstra(L), dijkstra(R); - for (int i = 0; i < N+K; ++i) D[i] = L[i]+R[i]; - dijkstra(D); - for (int i = 0; i < N; ++i) - cout << (D[i] < 1e18 ? D[i] : -1) << '\n'; -} - diff --git a/21/feb/plat/minimizing.cpp b/21/feb/plat/minimizing.cpp deleted file mode 100644 index 9d5bf95..0000000 --- a/21/feb/plat/minimizing.cpp +++ /dev/null @@ -1,78 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 1e5+5; - -int ans, D[2*MX]; -vector G[MX], H[2*MX]; - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - cin.tie(0)->sync_with_stdio(0); - - int T; cin >> T; - while (T--) { - int N, M; cin >> N >> M; - for (int u = 1; u <= N; ++u) G[u].clear(); - for (int u = 1; u <= 2*N; ++u) H[u].clear(); - for (int i = 0; i < M; ++i) { - int x, y; cin >> x >> y; - G[x].push_back(y), G[y].push_back(x); - H[x].push_back(y+N), H[y+N].push_back(x); - H[y].push_back(x+N), H[x+N].push_back(y); - } - - for (int u = 1; u <= 2*N; ++u) D[u] = 1e9; - queue q; - D[1] = 0, q.push(1); - while (q.size()) { - int u = q.front(); q.pop(); - for (int v : H[u]) if (D[v] == 1e9) - D[v] = D[u]+1, q.push(v); - } - - if (*max_element(D+1, D+2*N+1) == 1e9) { - cout << N-1 << '\n'; - continue; - } - - /*vector C; - C.emplace_back(0, 0); - for (int u = 1; u <= N; ++u) { - C.emplace_back(D[u], D[u+N]); - }*/ - - ans = 0; - map f; - map> b; - for (int u = 1; u <= N; ++u) { - ii p(min(D[u], D[u+N]), max(D[u], D[u+N])); - ++f[p], b[p].push_back(u); - } - map ea; - for (auto [p, c] : f) { - int pr = ea[ii(p.f-1, p.s+1)]; - if (p.f+1 == p.s) { - if (p.f == 0) ans += (c+1)/2; - else if (f[ii(p.f-1, p.s-1)]) ans += max((c-pr)+(pr+1)/2, (c+1)/2); - else { - if (pr < c) ans += c-pr; - ans += (c+1)/2; - } - } - else { - ans += c; - if (p.f == 0) ea[p] = c; - else if (f[ii(p.f-1, p.s-1)]) ea[p] += min(c, pr); - else { - if (pr < c) ans += c-pr; - ea[p] = c; - } - } - } - cout << ans << '\n'; - } -} diff --git a/21/feb/plat/notime.cpp b/21/feb/plat/notime.cpp deleted file mode 100644 index 48794bf..0000000 --- a/21/feb/plat/notime.cpp +++ /dev/null @@ -1,64 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 2e5+5, B = 300; - -int C[MX], L[MX], R[MX], ST[20][MX], ans[MX]; -pair P[MX]; - -inline int query(int i, int j) { - if (i > j) return MX; - int k = 31-__builtin_clz(j-i+1); - return min(ST[k][i], ST[k][j-(1<sync_with_stdio(0); - - int N, Q; cin >> N >> Q; - for (int i = 0; i < N; ++i) cin >> C[i]; - for (int i = 0; i < Q; ++i) { - cin >> P[i].f.f >> P[i].f.s; - --P[i].f.f, --P[i].f.s, P[i].s = i; - } - - vector tmp(N+1, -1); - for (int i = 0; i < N; ++i) L[i] = tmp[C[i]], tmp[C[i]] = i; - fill(begin(tmp), end(tmp), -1); - for (int i = N-1; i >= 0; --i) R[i] = tmp[C[i]], tmp[C[i]] = i; - - memset(ST, '?', sizeof ST); - for (int i = 0; i < N; ++i) ST[0][i] = C[i]; - for (int i = 0; i < 18; ++i) - for (int j = 0; j+(1<<(i+1)) < N; ++j) ST[i+1][j] = min(ST[i][j], ST[i][j+(1< b.f.s : a.f.s < b.f.s) : a.f.f/B < b.f.f/B; - }); - - int l = 0, r = -1, cur = 0; - for (int i = 0; i < Q; ++i) { - while (l > P[i].f.f) { - --l; - if (R[l] == -1 || R[l] > r || query(l+1, R[l]-1) < C[l]) ++cur; - } - while (r < P[i].f.s) { - ++r; - if (L[r] == -1 || L[r] < l || query(L[r]+1, r-1) < C[r]) ++cur; - } - while (l < P[i].f.f) { - if (R[l] == -1 || R[l] > r || query(l+1, R[l]-1) < C[l]) --cur; - ++l; - } - while (r > P[i].f.s) { - if (L[r] == -1 || L[r] < l || query(L[r]+1, r-1) < C[r]) --cur; - --r; - } - ans[P[i].s] = cur; - } - for (int i = 0; i < Q; ++i) cout << ans[i] << '\n'; -} diff --git a/21/open/balanced.cpp b/21/open/balanced.cpp deleted file mode 100644 index 02404a3..0000000 --- a/21/open/balanced.cpp +++ /dev/null @@ -1,118 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 155, MOD = 1e9+7; - -inline void add(int & x, int y) { x += y; if (x > MOD) x -= MOD; } - -string S[MX]; - -struct fenwick_tree_2d { - int FT[MX][MX]; - fenwick_tree_2d() { memset(FT, 0, sizeof FT); } - inline void update(int x, int y, int v) { - for (int i = x+1; i < MX; i += i&-i) - for (int j = y+1; j < MX; j += j&-j) add(FT[i][j], v); - } - inline int query(int x, int y) { - int ret = 0; - for (int i = x+1; i > 0; i -= i&-i) - for (int j = y+1; j > 0; j -= j&-j) add(ret, FT[i][j]); - return ret; - } - inline int query(int xl, int xr, int yl, int yr) { - int ret = query(xr, yr); - add(ret, MOD-query(xl-1, yr)); - add(ret, MOD-query(xr, yl-1)); - add(ret, query(xl-1, yl-1)); - return ret; - } -} DP[MX][4]; - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - cin.tie(0)->sync_with_stdio(0); - - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> S[i]; - - int ans = 0; - for (int i = 0; i < N; ++i) { - for (int a = 0; a < N; ++a) { - for (int b = a; b < N; ++b) { - if (S[i][b] != 'G') break; - - int sum = 1; - - int d0bb = DP[i][0].query(b,b); - int d0a1b = DP[i][0].query(a-1,b); - int d0ba1 = DP[i][0].query(b,a-1); - int d0a1a1 = DP[i][0].query(a-1,a-1); - // DP[i][0] query(b,b)-query(a-1,b)-query(b,a-1)+query(a-1,a-1); - // add(sum, DP[i][0].query(a, b, a, b)); - add(sum, d0bb), add(sum, MOD-d0a1b), add(sum, MOD-d0ba1), add(sum, d0a1a1); - DP[i+1][0].update(a, b, sum); - add(ans, sum); - - int d1bn1 = DP[i][1].query(b, N-1); - int d1a1n1 = DP[i][1].query(a-1, N-1); - int d1bb1 = DP[i][1].query(b,b-1); - int d1a1b1 = DP[i][1].query(a-1,b-1); - int d0bn1 = DP[i][0].query(b,N-1); - int d0a1n1 = DP[i][0].query(a-1,N-1); - // DP[i][1] query(b, N-1)-query(a-1,N-1)-query(b,b-1)+query(a-1, b-1) - // DP[i][0] query(b, N-1)-query(a-1, N-1)-query(b,b)+query(a-1, b) - // sum = DP[i][1].query(a, b, b, N-1); - sum = 0; add(sum, d1bn1), add(sum, MOD-d1a1n1), add(sum, MOD-d1bb1), add(sum, d1a1b1); - // add(sum, DP[i][0].query(a, b, b+1, N-1)); - add(sum, d0bn1), add(sum, MOD-d0a1n1), add(sum, MOD-d0bb), add(sum, d0a1b); - DP[i+1][1].update(a, b, sum); - add(ans, sum); - - int d2ab = DP[i][2].query(a, b); - //int d21b = 0; //DP[i][2].query(-1, b); - int d2aa1 = DP[i][2].query(a, a-1); - //int d21a1 = 0; //DP[i][2].query(-1, a-1); - //int d01b = 0; //DP[i][0].query(-1, b); - //int d01a1 = 0; //DP[i][0].query(-1, a-1); - // DP[i][2] query(a,b)-query(-1,b)-query(a, a-1)+query(-1, a-1) - // DP[i][0] query(a-1, b)-query(-1,b)-query(a-1,a-1)+query(-1,a-1) - // sum = DP[i][2].query(0, a, a, b); - sum = 0; add(sum, d2ab); //add(sum, MOD-d21b), - add(sum, MOD-d2aa1);//, add(sum, d21a1); - // add(sum, DP[i][0].query(0, a-1, a, b)); - add(sum, d0a1b);//, add(sum, MOD-d01b), - add(sum, MOD-d0a1a1);//, add(sum, d01a1); - DP[i+1][2].update(a, b, sum); - add(ans, sum); - - // int d01n1 = 0;//DP[i][0].query(-1,N-1); - // int d11n1 = 0;//DP[i][1].query(-1, N-1); - // int d11b1 = 0;//DP[i][1].query(-1, b-1); - int d2an1 = DP[i][2].query(a, N-1); - // int d21n1 = 0;//DP[i][2].query(-1, N-1); - // DP[i][3] query(a, N-1)-query(-1,N-1)-query(a,b-1)+query(-1, b-1) - // DP[i][0] query(a-1, N-1)-query(-1,N-1)-query(a-1,b)+query(-1, b) - // DP[i][1] query(a-1, N-1)-query(-1,N-1)-query(a-1,b-1)+query(-1, b-1) - // DP[i][2] query(a, N-1)-query(-1,N-1)-query(a,b)+query(-1, b) - sum = DP[i][3].query(a, N-1); add(sum, MOD-DP[i][3].query(a,b-1)); - // add(sum, DP[i][0].query(0, a-1, b+1, N-1)); - add(sum, d0a1n1);//, add(sum, MOD-d01n1), - add(sum, MOD-d0a1b);//, add(sum, d01b); - // add(sum, DP[i][1].query(0, a-1, b, N-1)); - add(sum, d1a1n1);//, add(sum, MOD-d11n1), - add(sum, MOD-d1a1b1);//, add(sum, d11b1); - // add(sum, DP[i][2].query(0, a, b+1, N-1)); - add(sum, d2an1); - //add(sum, MOD-d21n1), - add(sum, MOD-d2ab);//, add(sum, d21b); - DP[i+1][3].update(a, b, sum); - add(ans, sum); - } - } - } - cout << ans%MOD; -} diff --git a/21/open/balanced_slow.cpp b/21/open/balanced_slow.cpp deleted file mode 100644 index 3f7c3e9..0000000 --- a/21/open/balanced_slow.cpp +++ /dev/null @@ -1,73 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 155, MOD = 1e9+7; - -inline void add(int & x, int y) { x += y; if (x > MOD) x -= MOD; } - -string S[MX]; - -struct fenwick_tree_2d { - int FT[MX][MX]; - fenwick_tree_2d() { memset(FT, 0, sizeof FT); } - inline void update(int x, int y, int v) { - for (int i = x+1; i < MX; i += i&-i) - for (int j = y+1; j < MX; j += j&-j) add(FT[i][j], v); - } - inline int query(int x, int y) { - int ret = 0; - for (int i = x+1; i > 0; i -= i&-i) - for (int j = y+1; j > 0; j -= j&-j) add(ret, FT[i][j]); - return ret; - } - inline int query(int xl, int xr, int yl, int yr) { - int ret = query(xr, yr); - add(ret, MOD-query(xl-1, yr)); - add(ret, MOD-query(xr, yl-1)); - add(ret, query(xl-1, yl-1)); - return ret; - } -} DP[MX][4]; - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - cin.tie(0)->sync_with_stdio(0); - - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> S[i]; - - int ans = 0; - for (int i = 0; i < N; ++i) { - for (int a = 0; a < N; ++a) { - for (int b = a; b < N; ++b) { - if (S[i][b] != 'G') break; - - int sum = 1; - add(sum, DP[i][0].query(a, b, a, b)); - DP[i+1][0].update(a, b, sum); - add(ans, sum); - - sum = DP[i][1].query(a, b, b, N-1); - add(sum, DP[i][0].query(a, b, b+1, N-1)); - DP[i+1][1].update(a, b, sum); - add(ans, sum); - - sum = DP[i][2].query(0, a, a, b); - add(sum, DP[i][0].query(0, a-1, a, b)); - DP[i+1][2].update(a, b, sum); - add(ans, sum); - - sum = DP[i][3].query(0, a, b, N-1); - add(sum, DP[i][0].query(0, a-1, b+1, N-1)); - add(sum, DP[i][1].query(0, a-1, b, N-1)); - add(sum, DP[i][2].query(0, a, b+1, N-1)); - DP[i+1][3].update(a, b, sum); - add(ans, sum); - } - } - } - cout << ans%MOD; -} diff --git a/21/open/ucfj.cpp b/21/open/ucfj.cpp deleted file mode 100644 index e7d7475..0000000 --- a/21/open/ucfj.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -constexpr int MX = 2e5+5; - -int b[MX], l[MX], s[MX]; - -struct fenwick_tree { - int FT[MX]; - fenwick_tree() { memset(FT, 0, sizeof FT); } - inline void update(int x, int v) { if (++x) for (; x < MX; x += x&-x) FT[x] += v; } - inline int query(int x) { int ret = 0; if (++x) for (; x; x -= x&-x) ret += FT[x]; return ret; } - inline int query(int x, int y) { return query(y)-query(x-1); } -} range; - -struct seg_tree { - ll seg[4*MX], tmp[4*MX]; - seg_tree() { memset(seg, 0, sizeof seg), memset(tmp, 0, sizeof tmp); } - inline ll pull(ll a, ll b) { return a+b; } - inline void push(int l, int r, int n) { - if (tmp[n]) { - seg[n] += range.query(l, r) * 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 = MX-1, int n = 1) { - push(l, r, n); - if (l > r || l > b || r < a) return; - if (l >= a && r <= b) { tmp[n] += v, push(l, r, n); return; } - 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 = MX-1, int 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)); - } -} seg; - -int main() { - if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); - cin.tie(0)->sync_with_stdio(0); - - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> b[i]; - - memset(l, -1, sizeof l), memset(s, -1, sizeof s); - ll ans = 0; - for (int i = 0; i < N; ++i) { - if (l[b[i]] == -1) { - seg.update(0, i-2, 1); - } - else { - seg.update(s[b[i]]+1, l[b[i]]-1, -1); - seg.update(l[b[i]], l[b[i]], -seg.query(l[b[i]], l[b[i]])); - seg.update(l[b[i]]+1, i-2, 1); - range.update(l[b[i]], -1); - } - range.update(i, 1); - ans += seg.query(l[b[i]]+1, i-1); - s[b[i]] = l[b[i]], l[b[i]] = i; - } - cout << ans; -} diff --git a/22/feb/plat/sleeping.cpp b/22/feb/plat/sleeping.cpp deleted file mode 100644 index 4f1f5c8..0000000 --- a/22/feb/plat/sleeping.cpp +++ /dev/null @@ -1,78 +0,0 @@ -#include -#define f first -#define s second -using namespace std; -using ll = long long; -using ii = pair; -const int MX = 1e5+5; - -ll A[MX], P[MX], q[MX]; -int f[103680]; -vector> pr; - -int num_factors() { - int ret = 1; - for (auto & p : pr) ret *= p.s+1; - return ret; -} - -int & freq(ll x) { - ll code = 0; - for (auto & p : pr) { - int cnt = 0; - while (x%p.f == 0) x/= p.f, ++cnt; - code = (p.s+1)*code + min(p.s, cnt); - } - return f[code]; -} - -int main() { - cin.tie(0)->sync_with_stdio(0); - int N; cin >> N; - for (int i = 0; i < N; ++i) cin >> A[i]; - partial_sum(A, A+N, P); - ll sum = P[N-1]; - for (int p = 2; p < 1e6; ++p) { - if (sum%p == 0) { - int cnt = 0; - while (sum%p == 0) sum /= p, ++cnt; - pr.emplace_back(p, cnt); - } - } - for (int i = 0; i < N; ++i) { - ll tmp = gcd(P[i], sum); - if (tmp != 1 && tmp != sum) { - if (tmp > sum/tmp) tmp = sum/tmp; - if (tmp*tmp == sum) pr.emplace_back(tmp, 2); - else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1); - sum = 1; - } - } - int Q; cin >> Q; - for (int i = 0; i < Q; ++i) { - cin >> q[i]; - ll tmp = q[i]; - if (sum%tmp == 0 && tmp != 1 && tmp != sum) { - if (tmp > sum/tmp) tmp = sum/tmp; - if (tmp*tmp == sum) pr.emplace_back(tmp, 2); - else pr.emplace_back(tmp, 1), pr.emplace_back(sum/tmp, 1); - sum = 1; - } - } - if (sum > 1) pr.emplace_back(sum, 1); - for (int i = 0; i < N; ++i) ++freq(P[i]); - int block = 1; - for (int i = pr.size()-1; i >= 0; --i) { - for (int code = num_factors()-1; code >= 0; --code) - if (code/block%(pr[i].s+1)!=0) f[code-block] += f[code]; - block *= pr[i].s+1; - } - for (int i = 0; i < Q; ++i) { - if (P[N-1]%q[i]) cout << -1 << '\n'; - else { - ll ans = N+P[N-1]/q[i]; - ans -= freq(q[i])*2; - cout << ans << '\n'; - } - } -} diff --git a/7.5/nov/gold/telewire.cpp b/7.5/nov/gold/telewire.cpp new file mode 100644 index 0000000..e68ae69 --- /dev/null +++ b/7.5/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; +} -- cgit v1.2.3-70-g09d2