SHARE
TWEET

Toorcmmdc(#3393)

UnknownPrecentage Feb 18th, 2020 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream f("toorcmmdc.in");
  4. ofstream g("toorcmmdc.out");
  5. unordered_map <int, int> len, gcdv;
  6. unordered_multiset <int> groups[1500];
  7. unordered_multiset <int>::iterator it;
  8. int n, x, i, l;
  9. char ch;
  10. void cmmdc(int l)
  11. {
  12.     int gcd = -1;
  13.     for(int i = 1;i <= l;i++)
  14.         if(gcdv[i] != -1)
  15.         {
  16.             if(gcd != -1) gcd = __gcd(gcd, gcdv[i]);
  17.             else gcd = gcdv[i];
  18.         }
  19.     if(gcd == -1) gcd = 1;
  20.     g << gcd << "\n";
  21. }
  22. int update(unordered_multiset <int> &v)
  23. {
  24.     if(!v.size()) return -1;
  25.     int gcd = *v.begin();
  26.     for(auto i:v)
  27.         gcd = __gcd(gcd, i);
  28.     return gcd;
  29. }
  30. int main()
  31. {
  32.     f >> n;
  33.     while(n--)
  34.     {
  35.         f >> ch >> x;
  36.         if(ch == '+')
  37.         {
  38.             if(l == 0 || len[l] == 300)
  39.             {
  40.                 l++;
  41.                 gcdv[l] = x, len[l] = 1, groups[l].insert(x);
  42.             }
  43.             else
  44.             {
  45.                 if(len[l]) gcdv[l] = __gcd(gcdv[l], x);
  46.                 else gcdv[l] = x;
  47.                 len[l]++;
  48.                 groups[l].insert(x);
  49.             }
  50.             cmmdc(l);
  51.         }
  52.         else
  53.         {
  54.             for(i = 1;i <= l;i++)
  55.             {
  56.                 it = groups[i].find(x);
  57.                 if(groups[i].find(x) != groups[i].end())
  58.                 {
  59.                     groups[i].erase(it);
  60.                     len[i]--;
  61.                     gcdv[i] = update(groups[i]);
  62.                     break;
  63.                 }
  64.             }
  65.             cmmdc(l);
  66.         }
  67.     }
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top