Access control 20.08.13

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <bitset>
#include <iostream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

map<long long, char> m;

class Treap {
    struct TN {
        long long k;
        int p;
        TN *l, *r;
        TN(long long K) : k(K), p(rand()), l(0), r(0) {}
    } *t;
    TN *merge(TN *a, TN *b) {
        if (!a || !b)
            return a ? a : b;
        if (a->p > b->p) {
            a->r = merge(a->r, b);
            return a;
        } else {
            b->l = merge(a, b->l);
            return b;
        }
    }
    void split(TN *t, long long k, TN *&a, TN *&b) {
        if (!t) {
            a = b = 0;
            return;
        }
        if (t->k < k) {
            split(t->r, k, t->r, b);
            a = t;
        } else {
            split(t->l, k, a, t->l);
            b = t;
        }
    }
    void foreach(TN *n, char c) {
        if (!n)
            return;
        m.insert(make_pair(n->k, c));
        foreach(n->l, c);
        foreach(n->r, c);
    }
public:
    Treap() : t(0) {}
    void insert(long long k) {
        TN *t1, *t2;
        split(t, k, t1, t2);
        t = merge(merge(t1, new TN(k)), t2);
    }
    void foreach(long long k1, long long k2, char c) {
        TN * t1, *t2, *t3;
        split(t, k1, t1, t2);
        split(t2, k2 + 1, t2, t3);
        foreach(t2, c);
        t = merge(t1, t3);
    }
} t;

long long ip(long long a, long long b, long long c, long long d) {
    long long r = 0;
    r |= (a << 24);
    r |= (b << 16);
    r |= (c << 8);
    r |= d;
    return r;
}

char z[100010][50];
int n, k, a, b, c, d, q;
long long x[100010], y;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    freopen("access.in", "r", stdin);
    freopen("access.out", "w", stdout);

    scanf("%d\n", &n);
    for (int i = 0; i < n; i++)
        gets(z[i]);
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d.%d.%d.%d", &a, &b, &c, &d);
        x[i] = ip(a, b, c, d);
        t.insert(x[i]);
    }

    for (int i = 0; i < n; i++) {
        char mode = z[i][0] == 'a' ? 'A' : 'D';
        sscanf(z[i], "%*s%*s%d.%d.%d.%d", &a, &b, &c, &d);
        long long net = ip(a, b, c, d);
        if (!strchr(z[i], '/')) {
            t.foreach(net, net, mode);
        } else {
            sscanf(z[i], "%*s%*s%*d.%*d.%*d.%*d/%d", &q);
            q = 32 - q;
            long long mask = 1;
            mask = (mask << 32) - 1;
            mask = (mask << q) & mask;
            net &= mask;
            long long net2 = 1;
            net2 <<= q;
            net2--;
            t.foreach(net, net + net2, mode);
        }
    }

    for (int i = 0; i < k; i++) {
        printf("%c", m.find(x[i]) == m.end() ? 'A' : m[x[i]]);
    }

    return 0;
}