Mai intai trebuie sa te autentifici.
Cod sursa(job #1994826)
Utilizator | Data | 26 iunie 2017 11:20:20 | |
---|---|---|---|
Problema | Zoo | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.28 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()
{
ifstream in("zoo.in");
in >> n;
v.resize(n);
for(int i = 0; i < n; ++i)
in >> v[i].x >> v[i].y;
in >> m;
Query pos, neg;
pos.sign = 1;
neg.sign = -1;
int x1, y1, x2, y2;
for(int i = 1; i <= m; ++i)
{
in >> 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;
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;
}