diff options
author | Anthony Wang | 2022-03-15 20:38:51 -0500 |
---|---|---|
committer | Anthony Wang | 2022-03-15 20:38:51 -0500 |
commit | 896c6ceeff605c935a5538e3d9eca40ea3c79c56 (patch) | |
tree | 69d97b50f5ced801f6043cbef0219a941239f892 /17.5 | |
parent | 4c488e4c73f2d0e2b96bf0c444c05d42e566dd11 (diff) |
Restructure directories AGAIN so contests from the same season are in the same directory
Diffstat (limited to '17.5')
-rw-r--r-- | 17.5/feb/plat/gymnasts.cpp | 97 | ||||
-rw-r--r-- | 17.5/feb/plat/newbarn.cpp | 78 | ||||
-rw-r--r-- | 17.5/feb/plat/newbarn_naive.cpp | 72 | ||||
-rw-r--r-- | 17.5/open/plat/sort.cpp | 161 |
4 files changed, 408 insertions, 0 deletions
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 <algorithm> +#include <iostream> +#include <fstream> +#include <string> +#include <vector> +#include <queue> +#include <set> +#include <map> +#include <unordered_set> +#include <unordered_map> +#include <cmath> +#include <cstring> +#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(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<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd; +typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; +typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +template<int p> struct FF { + ll val; + + FF(const ll x = 0) { val = (x % p + p) % p; } + + bool operator==(const FF<p>& other) const { return val == other.val; } + bool operator!=(const FF<p>& other) const { return val != other.val; } + + FF operator+() const { return val; } + FF operator-() const { return -val; } + + FF& operator+=(const FF<p>& other) { val = (val + other.val) % p; return *this; } + FF& operator-=(const FF<p>& other) { *this += -other; return *this; } + FF& operator*=(const FF<p>& other) { val = (val * other.val) % p; return *this; } + FF& operator/=(const FF<p>& other) { *this *= other.inv(); return *this; } + + FF operator+(const FF<p>& other) const { return FF(*this) += other; } + FF operator-(const FF<p>& other) const { return FF(*this) -= other; } + FF operator*(const FF<p>& other) const { return FF(*this) *= other; } + FF operator/(const FF<p>& other) const { return FF(*this) /= other; } + + static FF<p> pow(const FF<p>& a, ll b) { + if (!b) return 1; + return pow(a * a, b >> 1) * (b & 1 ? a : 1); + } + + FF<p> pow(const ll b) const { return pow(*this, b); } + FF<p> inv() const { return pow(p - 2); } +}; + +template<int p> FF<p> operator+(const ll lhs, const FF<p>& rhs) { return FF<p>(lhs) += rhs; } +template<int p> FF<p> operator-(const ll lhs, const FF<p>& rhs) { return FF<p>(lhs) -= rhs; } +template<int p> FF<p> operator*(const ll lhs, const FF<p>& rhs) { return FF<p>(lhs) *= rhs; } +template<int p> FF<p> operator/(const ll lhs, const FF<p>& rhs) { return FF<p>(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 <algorithm> +#include <iostream> +#include <fstream> +#include <string> +#include <vector> +#include <queue> +#include <set> +#include <map> +#include <unordered_set> +#include <unordered_map> +#include <cmath> +#include <cstring> +#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL) +#define FOR(i, a, b, in) for (int i = (a); i < (b); i += in) +#define REP(i, a, b) for (int i = (a); i < (b); i++) +#define RFOR(i, a, b, in) for (int i = (a) - 1; i >= (b); i -= in) +#define RREP(i, a, b) for (int i = (a) - 1; i >= (b); i--) +#define trav(a, x) for (auto& a : x) +#define mp make_pair +#define pb push_back +#define lb lower_bound +#define ub upper_bound +#define sz(x) (int)x.size() +#define all(x) begin(x), end(x) +#define rsz resize +#define mem(a, b) memset(a, (b), sizeof(a)) +using namespace std; +typedef string str; +typedef long long ll; +typedef long double ld; +typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd; +typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; +typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +int 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 <algorithm> +#include <iostream> +#include <fstream> +#include <string> +#include <vector> +#include <queue> +#include <set> +#include <map> +#include <unordered_set> +#include <unordered_map> +#include <cmath> +#include <cstring> +#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL) +#define FOR(i, a, b, in) for (int i = (a); i < (b); i += in) +#define REP(i, a, b) for (int i = (a); i < (b); i++) +#define RFOR(i, a, b, in) for (int i = (a) - 1; i >= (b); i -= in) +#define RREP(i, a, b) for (int i = (a) - 1; i >= (b); i--) +#define trav(a, x) for (auto& a : x) +#define mp make_pair +#define pb push_back +#define f first +#define s second +#define lb lower_bound +#define ub upper_bound +#define sz(x) (int)x.size() +#define all(x) begin(x), end(x) +#define rsz resize +#define mem(a, b) memset(a, (b), sizeof(a)) +using namespace std; +typedef string str; +typedef long long ll; +typedef long double ld; +typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd; +typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; +typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +// 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 <algorithm> +#include <iostream> +#include <fstream> +#include <string> +#include <vector> +#include <queue> +#include <set> +#include <map> +#include <unordered_set> +#include <unordered_map> +#include <cmath> +#include <cstring> +#define init_io(pname) ifstream cin((string)pname+".in"); ofstream cout((string)pname+".out"); ios_base::sync_with_stdio(false); cin.tie(NULL) +#define FOR(i, a, b, in) for (int i = (a); i < (b); i += in) +#define REP(i, a, b) for (int i = (a); i < (b); i++) +#define RFOR(i, a, b, in) for (int i = (a) - 1; i >= (b); i -= in) +#define RREP(i, a, b) for (int i = (a) - 1; i >= (b); i--) +#define trav(a, x) for (auto& a : x) +#define mp make_pair +#define pb push_back +#define f first +#define s second +#define lb lower_bound +#define ub upper_bound +#define sz(x) (int)x.size() +#define all(x) begin(x), end(x) +#define rsz resize +#define mem(a, b) memset(a, (b), sizeof(a)) +using namespace std; +typedef string str; +typedef long long ll; +typedef long double ld; +typedef pair<int, int> ii; typedef pair<ll, ll> pl; typedef pair<ld, ld> pd; +typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; +typedef vector<ii> vii; typedef vector<pl> vpl; typedef vector<pd> vpd; +constexpr auto INF = (int)1e9; +constexpr auto LINF = (ll)1e18; + +template<typename T> class fenwick_tree { +private: vector<T> 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<T> 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<T>& 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<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 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<ii> 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<int> FT(N); + seg_tree<int> 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; +} |