Pagini recente » Cod sursa (job #604018) | Cod sursa (job #2034676) | Cod sursa (job #1271683) | Monitorul de evaluare | Cod sursa (job #1994828)
#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;
}