Cod sursa(job #1994828)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 26 iunie 2017 11:30:16
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class AIB
{
public:
    AIB(int sz)
    {
        v = new int[sz + 1];
        n = sz;
        for(int i = 1; i <= n; ++i)
            v[i] = 0;
    }
    ~AIB()
    {
        delete[] v;
    }
    void Add(int ind, int val)
    {
        while(ind <= n)
        {
            v[ind] += val;
            ind += ind & (-ind);
        }
    }
    int Query(int dr)
    {
        int ret = 0;
        while(dr >= 1)
        {
            ret += v[dr];
            dr -= dr & (-dr);
        }
        return ret;
    }
    int Query(int st, int dr)
    {
        return Query(dr) - Query(st - 1);
    }
private:
    int * v;
    int n;
};

struct Punct
{
    Punct(int x = 0, int y = 0)
    {
        this->x = x;
        this->y = y;
    }
    int x, y;
};

struct Query
{
    Query(int id = 0, int sign = 1, int ans = -1)
    {
        this->ans = ans;
        this->id = id;
        this->sign = sign;
    }
    int minX, maxX;
    int y;
    int ans, id;
    int sign; //1 or -1
};

const int nMax = 16005;
const int qMax = 100005;
const int valMax = 250000;

int n, m;
vector<Punct*> colPct[valMax]; //puncte pe coloana i
vector<Query*> colQuery[valMax]; //query pe coloana i
vector<Punct> v;
vector<Query> query;
int ans[qMax];

void citire()
{
    freopen("zoo.in", "r", stdin);
  //  ifstream in("zoo.in");
    scanf("%d", &n);
    v.resize(n);
    for(int i = 0; i < n; ++i)
        scanf("%d %d", &v[i].x, &v[i].y);
    scanf("%d", &m);
    query.reserve(2 * m);
    Query pos, neg;
    pos.sign = 1;
    neg.sign = -1;
    int x1, y1, x2, y2;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        pos.id = neg.id = i;
        pos.minX = neg.minX = x1;
        pos.maxX = neg.maxX = x2;
        pos.y = y2;
        neg.y = y1 - 1;
        query.push_back(pos);
        query.push_back(neg);
    }
 //   in.close();
}

inline bool cmp_y(const int *a, const int *b)
{
    return (*a < *b);
}

void normalize(vector<int*> &v)
{
    sort(v.begin(), v.end(), cmp_y);
    int k = 0, last;
    last = *v[0];
    *v[0] = k;
    for(int i = 1; i < v.size(); ++i)
    {
        if(*v[i] != last)
            ++k;
        last = *v[i];
        *v[i] = k;
    }
}

void Normalize()
{
    vector<int*> t;
    t.reserve(v.size() + query.size() * 2);
    for(auto &p:v)
        t.push_back(&(p.y));
    for(auto &q:query)
        t.push_back(&(q.y));
    normalize(t);

    t.clear();

    for(auto &p:v)
        t.push_back(&(p.x));
    for(auto &q:query)
        t.push_back(&(q.minX)), t.push_back(&(q.maxX));
    normalize(t);

}

void rezolvare()
{
    Normalize();
    for(auto &p:v)
        colPct[p.y].push_back(&p);
    for(auto &q:query)
        colQuery[q.y].push_back(&q);
    AIB aib(valMax);
    for(int i = 0; i < valMax; ++i)
    {
        for(auto &p:colPct[i])
            aib.Add(p->x + 1, 1);
        for(auto &q:colQuery[i])
            q->ans = aib.Query(q->minX + 1, q->maxX + 1);
    }
    for(auto &q:query)
        ans[q.id] += q.ans * q.sign;
}

void afisare()
{
    ofstream out("zoo.out");
    for(int i = 1; i <= m; ++i)
        out << ans[i] << "\n";
    out.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}