[My Contests] Stamford University Bangladesh Summer Contest 2019 (Replay)

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';
            }
      }
}