Hippskill

Untitled

Jan 25th, 2016
288
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <memory.h>
  8. #include <map>
  9. #include <set>
  10. #include <queue>
  11. #include <list>
  12. #include <sstream>
  13. #include <cstring>
  14. #include <cassert>
  15. #include <climits>
  16. using namespace std;
  17.  
  18. const int N = 350;
  19. const int blocksize = 400;
  20.  
  21. const int SZ = 5e7;
  22. char buf[SZ];
  23. int pos;
  24. void * operator new (size_t x){
  25.     pos += x;
  26. if (pos > SZ)
  27. throw 42;
  28. return buf + pos - x;
  29. }
  30. void operator delete(void *x) { }
  31.  
  32.  
  33. inline int gcd(int a, int b) {
  34.     while (b) {
  35.         a %= b;
  36.         swap(a, b);
  37.     }
  38.     return a;
  39. }
  40.  
  41. map<int, vector<int>> ind;
  42. int block[N];
  43. multiset<int> inblock[N];
  44. int id = 0;
  45. int maxblock = 0;
  46.  
  47. int query() {
  48.     int res = -1;
  49.     for (int i = 0; i <= maxblock; i++) {
  50.         if (block[i] == -1) continue;
  51.         res = res == -1 ? block[i] : gcd(res, block[i]);
  52.     }
  53.     return res;
  54. }
  55. void add(int x) {
  56.     while (inblock[id].size() >= blocksize) {
  57.         id++;
  58.         maxblock = max(maxblock, id);
  59.     }
  60.     inblock[id].insert(x);
  61.     int cur = -1;
  62.     for (auto v : inblock[id]) {
  63.         cur = cur == -1 ? v : gcd(cur, v);
  64.     }
  65.     ind[x].push_back(id);
  66.     block[id] = cur;
  67.    
  68. }
  69. void del(int x) {
  70.     int index = ind[x][ind[x].size() - 1];
  71.     ind[x].pop_back();
  72.     inblock[index].erase(inblock[index].find(x));
  73.     int cur = -1;
  74.     for (auto v : inblock[index]) {
  75.         cur = cur != -1 ? gcd(cur, v) : v;
  76.     }
  77.     block[index] = cur;
  78.     id = index;
  79. }
  80. char c;
  81. int main() {
  82.     //freopen("input.txt", "r", stdin);
  83.     //freopen("output.txt", "w", stdout);
  84.     int n;
  85.     scanf("%d", &n);
  86.     for (int i = 0; i < N; i++)
  87.         block[i] = -1;
  88.     for (int i = 0; i < n; i++) {
  89.         int x;
  90.         scanf("%s%d", &c, &x);
  91.         if (c == '+') {
  92.             add(x);
  93.         }
  94.         else {
  95.             del(x);
  96.         }
  97.         int ans = query();
  98.         printf("%d\n", ans != -1 ? ans : 1);
  99.     }
  100.     return 0;
  101. }
RAW Paste Data