Contest Link : Stamford University Bangladesh Summer Contest 2019 (Replay)
Standings : https://toph.co/c/stamford-summer-2019-r/standings
Problem : A. Lucky Shirt
Category : Number Thory, Data Structure
Topic : Euler Phi Function, Wavelet Tree
#include <bits/stdc++.h>
using namespace std;
static const int maxn = 2e5 + 5;
int phi[maxn];
void eularPhi()
{
for (int i = 1; i < maxn; i++) phi[i] = i;
for (int p = 2; p < maxn; p++)
{
if (phi[p] == p)
{
for (int k = p; k < maxn; k += p)
{
phi[k] -= phi[k]/p;
}
}
}
}
struct Tree
{
#define vi vector <int>
#define pb push_back
int lo, hi;
Tree *l, *r;
vi b;
Tree(int *from , int *to, int x, int y)
{
lo = x, hi = y;
if (from >= to || lo == hi) return;
int mid = (lo + hi) >> 1;
auto f = [mid](int x)
{
return x <= mid;
};
b.reserve(to-from+1);
b.pb(0); // for making 1 indexed
for (auto it = from; it != to; it++) b.pb(b.back() + f(*it));
auto pivot = stable_partition(from, to, f);
l = new Tree(from, pivot, lo, mid);
r = new Tree(pivot, to, mid+1, hi);
}
inline int EQL(int l, int r, int k)
{
if (l > r || k < lo || k > hi) return 0;
if (lo == hi) return (r - l + 1);
int lb = b[l-1];
int rb = b[r];
int mid = (lo + hi) >> 1;
if (k <= mid) return this->l->EQL(lb+1, rb, k);
return this->r->EQL(l-lb, r-rb, k);
}
~Tree()
{
delete l;
delete r;
}
};
int temp[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(8);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// #endif // ONLINE_JUDGE
eularPhi();
int n, q;
cin >> n >> q;
int maxi = 0;
for (int i = 1; i <= n; i++)
{
temp[i] = phi[i];
maxi = max(maxi, phi[i]);
}
Tree *tree;
tree = new Tree(temp+1, temp+n+1, 1, maxi);
while (q--)
{
int l, r, x;
cin >> l >> r >> x;
int ans = tree->EQL(l, r, x);
cout << ans << '\n';
}
}
Problem : B. Match the Range
Category : Data Structure, Random Number Generate
Topic : Wavelet Tree, Random Number Generate
#include <bits/stdc++.h>
using namespace std;
static const int maxn = 2e5 + 5;
struct Tree
{
#define vi vector <int>
#define pb push_back
int lo, hi;
Tree *l, *r;
vi b;
Tree(int *from , int *to, int x, int y)
{
lo = x, hi = y;
if (from >= to || lo == hi) return;
int mid = (lo + hi) >> 1;
auto f = [mid](int x)
{
return x <= mid;
};
b.reserve(to-from+1);
b.pb(0); // for making 1 indexed
for (auto it = from; it != to; it++) b.pb(b.back() + f(*it));
auto pivot = stable_partition(from, to, f);
l = new Tree(from, pivot, lo, mid);
r = new Tree(pivot, to, mid+1, hi);
}
inline int LTE(int l, int r, int k)
{
if (l > r || k < lo) return 0;
if (hi <= k) return (r - l + 1);
int lb = b[l-1];
int rb = b[r];
return this->l->LTE(lb+1, rb, k) + this->r->LTE(l-lb, r-rb, k);
}
inline int EQL(int l, int r, int k)
{
if (l > r || k < lo || k > hi) return 0;
if (lo == hi) return (r - l + 1);
int lb = b[l-1];
int rb = b[r];
int mid = (lo + hi) >> 1;
if (k <= mid) return this->l->EQL(lb+1, rb, k);
return this->r->EQL(l-lb, r-rb, k);
}
int kth(int l, int r, int k)
{
if (l > r) return 0;
if (lo == hi) return lo;
int lb = b[l-1];
int rb = b[r];
int inLeft = rb - lb;
if (k <= inLeft) return this->l->kth(lb + 1, rb, k);
else return this->r->kth(l - lb, r - rb, k - inLeft);
}
~Tree()
{
delete l;
delete r;
}
};
int arr[maxn];
long long cumsum[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(8);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// #endif // ONLINE_JUDGE
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
cumsum[i] = cumsum[i-1] + arr[i];
}
int maxi = *max_element(arr+1, arr+n+1);
Tree *tree;
tree = new Tree(arr+1, arr+n+1, 1, maxi);
mt19937 rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
while (q--)
{
int a, b, x, y;
cin >> a >> b >> x >> y;
if (a > b) swap(a, b);
if (x > y) swap(x, y);
long long sum1 = cumsum[b] - cumsum[a-1];
long long sum2 = cumsum[y] - cumsum[x-1];
if (b-a+1 != y-x+1 || sum1 != sum2)
{
cout << "No\n";
continue;
}
int op = 80;
bool ok = true;
while (op--)
{
int idx = uniform_int_distribution <int> (1, b-a+1)(rng);
assert(idx >= 1 && idx <= b-a+1);
int kth_1 = tree->kth(a, b, idx);
int kth_2 = tree->kth(x, y, idx);
int ls_1 = tree->LTE(a, b, kth_1);
int ls_2 = tree->LTE(x, y, kth_2);
if (kth_1 != kth_2 || ls_1 != ls_2)
{
ok = false;
break;
}
}
if (ok) cout << "Yes\n";
else cout << "No\n";
}
}
Problem : C. Minimize the Odds
Category : Add Hoc
Topic : Add Hoc
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(8);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// #endif // ONLINE_JUDGE
int n;
cin >> n;
int odd = 0;
for (int i = 1; i <= n; i++)
{
ll x;
cin >> x;
if (x & 1) ++odd;
}
if (odd & 1) odd = 1;
else odd = 0;
cout << odd << endl;
}
Problem : D. Squares Inside Square
Category : Combinatorics
Topic : Counting
tc = int(input())
for tcase in range(1, tc+1, 1):
n = int(input())
ans = int(n*(n+1)*(2*n+1))
ans = ans//6
print(ans)
Problem : E. Giveaway
Category : Add Hoc
#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(15);
cout << 1 << endl;
}
Problem : F. Arshiya's Sector
Category : Geometry
Type : Basic Geometry
#include <bits/stdc++.h>
using namespace std;
#define pi 2*acos(0.0)
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(8);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// #endif // ONLINE_JUDGE
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
double r, ang;
cin >> r >> ang;
double area = pi * r * r * (ang / 360.0);
cout << area << endl;
}
}
Problem : G. Remove Duplicates
Category : Add Hoc
Type : Implementation
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(8);
// #ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
// #endif // ONLINE_JUDGE
int tc;
cin >> tc;
for (int tcase = 1; tcase <= tc; tcase++)
{
string s;
cin >> s;
map <char, int> Map;
for (char ch : s) ++Map[ch];
set <char> vis;
cout << "Case #" << tcase << ":\n";
for (char ch : s)
{
if (vis.find(ch) != vis.end()) continue;
vis.insert(ch);
cout << ch << " " << Map[ch] << '\n';
}
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.