Cod sursa(job #1099112)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 5 februarie 2014 16:09:55
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.84 kb
#include <vector>
#include <algorithm>

#include <cstdio>
using namespace std;

const int MAX_N = 16002;

int N, M;
char s[55];
vector < int > A[3 * MAX_N], temp;
pair < int, int > v[MAX_N];

void update(int node, int st, int dr, int x, int val) {
    if(st == dr)
        A[node].push_back(val);
    else {
        int ls = 2 * node, rs = 2 * node + 1, m = (st + dr) / 2;

        if(x <= m)
            update(ls, st, m, x, val);
        else update(rs, m + 1, dr, x, val);

        A[node].push_back(val);
    }
}

int query(int node, int st, int dr, int x, int y, int val1, int val2) {
    if(x > y)
        return 0;
    if(x <= st && dr <= y)
        return upper_bound(A[node].begin(), A[node].end(), val2) - lower_bound(A[node].begin(), A[node].end(), val1);
    else {
        int ls = 2 * node, rs = 2 * node + 1, m = (st + dr) / 2, ret = 0;

        if(x <= m)
            ret += query(ls, st, m, x, y, val1, val2);
        if(y > m)
            ret += query(rs, m + 1, dr, x, y, val1, val2);

        return ret;
    }
}

int main() {
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    scanf("%d", &N);
    fgets(s, 3, stdin);
    for(int i = 1; i <= N; ++i) {
        fgets(s, 55, stdin);

        int sign = 0;
        bool ok = 1, ok1 = 0;
        for(int j = 0; ok; ++j) {
            if(s[j] >= '0' && s[j] <= '9') {
                if(j > 0 && s[j - 1] == '-')
                    sign = -1;
                else sign = 1;

                int temp = 0;
                while(s[j] >= '0' && s[j] <= '9')
                    temp = temp * 10 + s[j] - '0', ++j;
                temp *= sign;

                if(!ok1)
                    v[i].first = temp, ok1 = 1;
                else {
                    v[i].second = temp;
                    ok = 0;
                }
            }
        }
    }

    vector < int > temp2;
    for(int i = 1; i <= N; ++i)
        temp2.push_back(v[i].first);

    sort(temp2.begin(), temp2.end());
    temp.push_back(-2000000001);
    temp.push_back(temp2[0]);
    for(size_t i = 1; i < temp2.size(); ++i)
        if(temp2[i] != temp2[i - 1])
            temp.push_back(temp2[i]);


    for(int i = 1; i <= N; ++i) {
        v[i].first = lower_bound(temp.begin(), temp.end(), v[i].first) - temp.begin();
        swap(v[i].first, v[i].second);
    }
    sort(v + 1, v + N + 1);

    for(int i = 1; i <= N; ++i)
        update(1, 1, N, v[i].second, v[i].first);

    scanf("%d", &M);
    fgets(s, 3, stdin);
    for(int i = 1, X1, Y1, X2, Y2; i <= M; ++i) {
        fgets(s, 50, stdin);

        X1 = Y1 = X2 = Y2 = 0;

        int sign = 0;
        bool ok = 1, ok1 = 0, ok2 = 0, ok3 = 0;
        for(int j = 0; ok; ++j) {
            if(s[j] >= '0' && s[j] <= '9') {
                if(j > 0 && s[j - 1] == '-')
                    sign = -1;
                else sign = 1;

                int temp = 0;
                while(s[j] >= '0' && s[j] <= '9')
                    temp = temp * 10 + s[j] - '0', ++j;
                temp *= sign;

                if(!ok1)
                    X1 = temp, ok1 = 1;
                else if(!ok2)
                    Y1 = temp, ok2 = 1;
                else if(!ok3)
                    X2 = temp, ok3 = 1;
                else {
                    Y2 = temp;
                    ok = 0;
                }
            }
        }

        int x = 0;
        for(int l = 0, r = temp.size() - 1, m; l <= r; ) {
            m = (l + r) / 2;
            if(temp[m] >= X1)
                x = m, r = m - 1;
            else l = m + 1;
        }
        X1 = x;

        x = temp.size() - 1;
        for(int l = 0, r = temp.size() - 1, m; l <= r; ) {
            m = (l + r) / 2;
            if(temp[m] > X2)
                r = m - 1;
            else x = m, l = m + 1;
        }
        X2 = x;

        printf("%d\n", query(1, 1, N, X1, X2, Y1, Y2));
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}