Advertisement
ice_tea

Untitled

Jul 24th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.83 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define eps 1e-7
  4. #define inf 1e9
  5. #define linf 1e18
  6. #define pb push_back
  7. #define mod 1e9 + 7
  8. #define mp make_pair
  9. #define ld long double
  10. #define pi 3.141592653589793238462643
  11. using namespace std;
  12.  
  13. ll null = 0;
  14.  
  15. struct segment;
  16. struct line;
  17. struct point;
  18. struct vec;
  19. struct ray;
  20.  
  21. struct point{
  22.     ld x, y;
  23.     point(){}
  24.     point(ld x1, ld y1){
  25.         x = x1;
  26.         y = y1;
  27.     }
  28.     ld dist_to_point(point p){
  29.         return sqrt((p.x - x) * (p.x - x) + (p.y - y) * (p.y - y));
  30.     }
  31.     bool operator < (point p){
  32.         return (x < p.x) || ((x == p.x) && (y < p.y));
  33.     }
  34. };
  35.  
  36. struct vec{
  37.     ld x, y;
  38.     vec (ld x1, ld y1){
  39.         x = x1;
  40.         y = y1;
  41.     }
  42.     vec (point a, point b){
  43.         x = b.x - a.x;
  44.         y = b.y - a.y;
  45.     }
  46.     vec normal(){
  47.         vec ans;
  48.         ans.x = y;
  49.         ans.y = -x;
  50.         return ans;
  51.     }
  52.     vec opposite(){
  53.         vec ans;
  54.         ans.x = -x;
  55.         ans.y = -y;
  56.         return ans;
  57.     }
  58.     vec sum(vec b){
  59.         vec ans;
  60.         ans.x = x + b.x;
  61.         ans.y = y + b.y;
  62.         return ans;
  63.     }
  64.     ld cross_product(vec v){
  65.         return x * v.y - v.x * y;
  66.     }
  67.     ld dot_product(vec v){
  68.         return x * v.x + y * v.y;
  69.     }
  70.     vec resize(ld size){
  71.         vec ans;
  72.         ans.x = (x * size) / len();
  73.         ans.y = (y * size) / len();
  74.         return ans;
  75.     }
  76.     vec(){}
  77.     ld len(){
  78.         return sqrt(x * x + y * y);
  79.     }
  80. };
  81.  
  82.  
  83. struct line{
  84.     ld a, b, c;
  85.     line (point a1, point b1){
  86.         a = a1.y - b1.y;
  87.         b = b1.x - a1.x;
  88.         c = -a1.x * a - a1.y * b;
  89.     }
  90.     line (ld a1, ld b1, ld c1){
  91.         a = a1;
  92.         b = b1;
  93.         c = c1;
  94.     }
  95.     line(){}
  96.     vec normal_vec(){
  97.         vec ans;
  98.         ans.x = a;
  99.         ans.y = b;
  100.         return ans;
  101.     }
  102.     line normal_line(point p){
  103.         line ans;
  104.         ans.a = -b;
  105.         ans.b = a;
  106.         ans.c = -ans.a * p.x - ans.b * p.y;
  107.         return ans;
  108.     }
  109.     ld get_x(ld y1){
  110.         if (a == 0) return 0;
  111.         return (-c - b * y1) / a;
  112.     }
  113.     ld get_y(ld x1){
  114.         if (b == 0) return 0;
  115.         return (-c - a * x1) / b;
  116.     }
  117.     point intersection(line l){
  118.         point ans;
  119.         ans.x = (-c * l.b + l.c * b) / (a * l.b - l.a * b);
  120.         ans.y = (-a * l.c + l.a * c) / (a * l.b - l.a * b);
  121.         return ans;
  122.     }
  123.     ld dist_to_point(point p){
  124.         return abs((a * p.x + b * p.y + c) / (sqrt(a * a + b * b)));
  125.     }
  126.     ll is_inside(point p){
  127.         ld k = a * p.x + b * p.y + c;
  128.         if (k < 0) return -1;
  129.         else if (k == 0) return 0;
  130.         return 1;
  131.     }
  132. };
  133.  
  134. struct segment{
  135.     point a, b;
  136.     segment(){}
  137.     segment(point a1, point b1){
  138.         a = a1;
  139.         b = b1;
  140.     }
  141.     ld len(){
  142.         return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  143.     }
  144.     bool is_inside(point p){
  145.         line l(a, b);
  146.         if (l.is_inside(p) != 0) return false;
  147.         vec v(p, a), v1(p, b);
  148.         if (v.dot_product(v1) > 0) return false;
  149.         return true;
  150.     }
  151.     long double dist_to_point(point p){
  152.         vec v(a, p), v1(a, b), v2(b, p), v3(b, a);
  153.         if (v.dot_product(v1) < 0) return p.dist_to_point(a);
  154.         if (v2.dot_product(v3) < 0) return p.dist_to_point(b);
  155.         line l(a, b);
  156.         return l.dist_to_point(p);
  157.     }
  158.     point get_center(){
  159.         point ans;
  160.         ans.x = (a.x + b.x) / 2;
  161.         ans.y = (a.y + b.y) / 2;
  162.         return ans;
  163.     }
  164. };
  165.  
  166. struct ray{
  167.     point a, b;
  168.     ray(point p, point p1){
  169.         a = p;
  170.         b = p1;
  171.     }
  172.     ray(){}
  173.     ld dist_to_point(point p){
  174.         vec v(a, p), v1(a, b);
  175.         if (v.dot_product(v1) < 0) return a.dist_to_point(p);
  176.         line l(a, b);
  177.         return l.dist_to_point(p);
  178.     }
  179.     bool is_inside(point p){
  180.         line l(a, b);
  181.         if (l.is_inside(p) != 0) return false;
  182.         vec v(a, p), v1(a, b);
  183.         if (v.dot_product(v1) < 0) return false;
  184.         return true;
  185.     }
  186. };
  187.  
  188. struct angle{
  189.     point a, b, c;
  190.     angle(){};
  191.     angle (point a1, point b1, point c1){
  192.         a = a1;
  193.         b = b1;
  194.         c = c1;
  195.     }
  196.     ld get_angle(){
  197.         vec v(b, a), v1(b, c);
  198.         cout<<v.dot_product(v1)<<" "<<v.len()<<" "<<v1.len()<<endl;
  199.         return acos(v.dot_product(v1) / (v.len() * v1.len()));
  200.     }
  201. };
  202.  
  203. struct polygon{
  204.     ll n;
  205.     vector <point> points;
  206.     ld get_area(){
  207.         point a(0, 0);
  208.         vec v(a, points[0]);
  209.         ld ans = 0;
  210.         for (ll i = 1; i < n; ++i){
  211.             vec v1(a, points[i]);
  212.             ans = ans + v.cross_product(v1);
  213.             v = v1;
  214.         }
  215.         vec v2(a, points[0]);
  216.         vec v1(a, points[n - 1]);
  217.         return abs(ans + v1.cross_product(v2)) / 2;
  218.     }
  219. };
  220.  
  221. struct triangle{
  222.     point a, b, c;
  223.     triangle(){}
  224.     triangle(point a1, point b1, point c1){
  225.         a = a1;
  226.         b = b1;
  227.         c = c1;
  228.     }
  229.     ld get_area(){
  230.         point d(0, 0);
  231.         vec v(a, d), v1(b, d), v2(c, d);
  232.         return (v.cross_product(v1) + v1.cross_product(v2) + v2.cross_product(v)) / 2;
  233.     }
  234.     point get_center(){
  235.         segment s(a, b), s1(a, c);
  236.         point p = s.get_center(), p1 = s1.get_center();
  237.         line l(a, b), l1(a, c), l2(b, c);
  238.         l = l.normal_line(p);
  239.         l1 = l1.normal_line(p1);
  240.         return l.intersection(l1);
  241.     }
  242.     ld get_R(){
  243.         triangle t(a, b, c);
  244.         point p = t.get_center();
  245.         return p.dist_to_point(a);
  246.     }
  247. };
  248.  
  249. ll power(ll a, ll b){
  250.     if (b == 0) return 1;
  251.     else if (b == 1) return a;
  252.     else {
  253.         ll k = power(a, b / 2);
  254.         return k * k * power(a, b % 2);
  255.     }
  256. }
  257.  
  258. ll power_mod(ll a, ll b, ll MOD){
  259.     if (b == 0) return 1;
  260.     else if (b == 1) return a % MOD;
  261.     else{
  262.         ll k = power_mod(a, b / 2, MOD);
  263.         return ((k * k) % MOD * power_mod(a, b % 2, MOD)) % MOD;
  264.     }
  265. }
  266.  
  267. ll sum_mod(ll a, ll b, ll MOD){
  268.     return (a + b) % MOD;
  269. }
  270.  
  271. ll mul_mod(ll a, ll b, ll MOD){
  272.     return (a * b) % MOD;
  273. }
  274.  
  275. ll ord(char a){
  276.     return a;
  277. }
  278.  
  279. char chr(ll a){
  280.     return a;
  281. }
  282.  
  283. ll strtoint(string s){
  284.     ll ans = 0;
  285.     for (ll i = 0; i < s.size(); ++i){
  286.         ans *= 10;
  287.         ans += ord(s[i]) - 48;
  288.     }
  289.     return ans;
  290. }
  291.  
  292. string rev_string(string s){
  293.     string ans = "";
  294.     for (ll i = s.size(); i >= 0; --i){
  295.         ans += s[i];
  296.     }
  297.     return ans;
  298. }
  299.  
  300. string inttostr(ll a){
  301.     string ans = "", ans1 = "";
  302.     while (a > 0){
  303.         ans += chr(a + 48);
  304.         a /= 10;
  305.     }
  306.     for (ll i = ans.size() - 1; i >= 0; --i){
  307.         ans1 += ans[i];
  308.     }
  309.     return ans1;
  310. }
  311.  
  312. /*
  313. _________________________________________________________________________________________________________________________________________________
  314. start programm
  315. _________________________________________________________________________________________________________________________________________________
  316. */
  317.  
  318. #define len 26000
  319.  
  320. struct bor{
  321.     vector <vector <ll> > ar;
  322.     ll arr[len];
  323.     ll n;
  324.     bor(){
  325.         ar.resize(len);
  326.         for (ll i = 0; i < len; ++i){
  327.             ar[i].resize(2);
  328.             ar[i][0] = -1;
  329.             ar[i][1] = -1;
  330.             arr[i] = 0;
  331.         }
  332.         n = 0;
  333.     }
  334.     void add(ll x){
  335.         vector <bool> ar1;
  336.         for (ll i = 0; i < 30; ++i){
  337.             ar1.pb(x % 2 == 0);
  338.             x /= 2;
  339.         }
  340.         ll k = 0;
  341.         for (ll i = ar1.size(); i >= 0; --i){
  342.             ++arr[k];
  343.             if (ar[k][ar1[i]] == -1){
  344.                 ++n;
  345.                 if (n >= len) cout<<"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA, HELP"<<endl;
  346.                 ar[k][ar1[i]] = n;
  347.                 k = n;
  348.             }
  349.             else k = ar[k][ar1[i]];
  350.         }
  351.         ++arr[k];
  352.     }
  353.     void del(ll x){
  354.         vector <bool> ar1;
  355.         for (ll i = 0; i < 30; ++i){
  356.             ar1.pb(x % 2 == 0);
  357.             x /= 2;
  358.         }
  359.         ll k = 0, t = -1, p = -1;
  360.         for (ll i = ar1.size(); i >= 0; --i){
  361.             --arr[k];
  362.             if ((arr[k] == 0) && (t != -1)){
  363.                 //cout<<"OMAGAOMAGA"<<endl;
  364.                 ar[t][p] = -1;
  365.             }
  366.             t = k;
  367.             p = ar1[i];
  368.             k = ar[k][ar1[i]];
  369.         }
  370.         if ((arr[k] == 0) && (t != -1)){
  371.             //cout<<"OMAGAOMAGA1"<<endl;
  372.             ar[t][p] = -1;
  373.         }
  374.     }
  375.     ll get(ll x){
  376.         vector <pair<bool, ll> > ar1;
  377.         ll f = 1;
  378.         for (ll i = 0; i < 30; ++i){
  379.             ar1.pb(mp((x % 2 == 0), f));
  380.             f *= 2;
  381.             x /= 2;
  382.         }
  383.         ll k = 0, ans = 0;
  384.         for (ll i = ar1.size(); i >= 0; --i){
  385.             ll a = (!ar1[i].first);
  386.             //cout<<ar[k][0]<<" "<<ar[k][1]<<endl;
  387.             if (ar[k][a] == -1) k = ar[k][ar1[i].first];
  388.             else{
  389.                 ans += ar1[i].second;
  390.                 k = ar[k][a];
  391.             }
  392.         }
  393.         return ans;
  394.     }
  395. };
  396.  
  397.  
  398. int main(){
  399.     ios_base::sync_with_stdio(0);
  400.     cin.tie(0);
  401.     cout.tie(0);
  402.     srand(time(0));
  403.     ll q;
  404.     cin>>q;
  405.     bor s;
  406.     for (ll i = 0; i < q; ++i){
  407.         char c;
  408.         ll a;
  409.         cin>>c>>a;
  410.         if (c == '+') s.add(a);
  411.         else if (c == '-') s.del(a);
  412.         else cout<<s.get(a)<<endl;
  413.     }
  414. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement