Cod sursa(job #1913894)

Utilizator ajeccAjechiloae Eugen ajecc Data 8 martie 2017 14:34:59
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.33 kb
#include <bits/stdc++.h>
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(stream, s) getline(stream, s)
#define FASTIO ios_base::sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int CHARMAX = (1 << 10);
const int INFINT = 2000000000 + 100;
const ll INFLL = (1LL << 62);

/*class InParsare
{
private:
    FILE *fin;
    char *buffer;
    size_t index_of_buffer;

    char read_character()
    {
        index_of_buffer++;
        if(index_of_buffer == CHARMAX)
        {
            fread(buffer, 1, CHARMAX, fin);
            index_of_buffer = 0;
        }
        return buffer[index_of_buffer];
    }

public:
    InParsare(const char *name)
    {
        fin = fopen(name, "r");
        buffer = new char[CHARMAX]();
        index_of_buffer = CHARMAX - 1;
    }

    template<class T>
    InParsare &operator >> (T &n)
    {
        char c;
        while(!isdigit(c = read_character()) && c != '-');

        int sgn = 1;
        if(c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else n = c - '0';

        while(isdigit(c = read_character()))
            n = n * 10 + c - '0';
        n *= sgn;

        return *this;
    }
};

class OutParsare
{
private:
    FILE *fout;
    char *buffer;
    size_t index_of_buffer;

    void write_character(char character)
    {
        if(index_of_buffer == CHARMAX)
        {
            fwrite(buffer, 1, CHARMAX, fout);
            index_of_buffer = 0;
            buffer[index_of_buffer++] = character;
        }
        else buffer[index_of_buffer++] = character;
    }

public:

    OutParsare(const char *name)
    {
        fout = fopen(name, "w");
        buffer = new char[CHARMAX]();
        index_of_buffer = 0;
    }

    ~OutParsare()
    {
        fwrite(buffer, 1, index_of_buffer, fout);
        fclose(fout);
    }
    template<class T>
    OutParsare &operator << (T n)
    {
        if(typeid(T).name() == typeid(char).name())
        {
            write_character(n);
            return *this;
        }

        if(n <= 9)
            write_character(n + '0');
        else
        {
            (*this) << (n / 10);
            write_character(n % 10 + '0');
        }

        return *this;
    }

};*/

//InParsare fin("zoo.in"); /// merg numai pt numere
//OutParsare fout("zoo.out"); /// merg numai pt numere + caractere individuale, nu stringuri
//ifstream fin("zoo.in");
//ofstream fout("zoo.out");

const int NMAX = 4 * 1e5 + 100;
const int MOD = 666013;
const double EPS = 0.000000001;

int n, m;

struct pct
{
    int x, y;
};

inline bool cmp(pct l, pct r)
{
    if(l.x == r.x)
        return l.y <= r.y;
    return l.x < r.x;
}

pct v[NMAX];

struct mlc
{
    bool query;
    int val;
    int index;
    int l, r, nr_query;
};

mlc arr[NMAX];
size_t ssize;
inline bool cmp2(mlc l, mlc r)
{
    if(l.val != r.val)
        return l.val > r.val;
    return l.query <= r.query;
}

int bit[NMAX];

inline int lsb(int x)
{
    return x & (-x);
}

inline void update(int pos)
{
    for(; pos <= ssize; pos += lsb(pos))
        bit[pos]++;
}

inline int query(int pos)
{
    int ret = 0;
    for(; pos >= 1; pos -= lsb(pos))
        ret += bit[pos];
    return ret;
}

int sol[NMAX];

inline bool plm(pct a, pct b)
{
    return a.x < b.x;
}

int main()
{
    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);
    //fin >> n;
    scanf("%d", &n);
    for1(i, n)
    {
       // fin >> v[i].x >> v[i].y;
       scanf("%d %d", &v[i].x, &v[i].y);
    }

    sort(v + 1, v + n + 1, cmp);
    for1(i, n)
    {
        mlc temp;
        temp.query = 0;
        temp.val = v[i].y;
        temp.index = i;
        arr[i] = temp;
    }
    ssize = n;
   // fin >> m;
    scanf("%d", &m);
    for1(i, m)
    {
        sol[i] = -INFINT;
        int x1, y1, x2, y2;
       // fin >> x1 >> y1 >> x2 >> y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        pct aux;
        aux.y = -INFINT;
        aux.x = x1;
        int index1 = lower_bound(v + 1, v + n + 1, aux, plm) - v;
        aux.x = x2;
        int index2 = upper_bound(v + 1, v + n + 1, aux, plm) - v - 1;

       // cout << index1 << ' ' << index2 << '\n';
        mlc temp;
        temp.query = 1;
        temp.l = index1;
        temp.r = index2;
        temp.nr_query = i;
        temp.val = y1;
        arr[++ssize] = temp;
        temp.val = y2 + 1;
        arr[++ssize] = temp;
    }

    sort(arr + 1, arr + ssize + 1, cmp2);
    for1(i, ssize)
    {
        //cout << arr[i].query << ' ' << arr[i].val  << '\n';
        if(!arr[i].query)
        {
            update(arr[i].index);
            continue;
        }

        if(sol[arr[i].nr_query] == -INFINT) sol[arr[i].nr_query] = -(query(arr[i].r) - query(arr[i].l - 1));
        else sol[arr[i].nr_query] += query(arr[i].r) - query(arr[i].l - 1);
    }

    for1(i, m)
        //fout << sol[i] << '\n';
        printf("%d\n", sol[i]);



    return 0;
}