Pagini recente » Cod sursa (job #620431) | Cod sursa (job #2264668) | Cod sursa (job #2750739)
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
const int NMAX = 16000;
unordered_map<int, int> normX;
unordered_map<int, int> normY;
vector<int> coordX;
vector<int> coordY;
vector<pair<int, int>> puncte;
int mat[1 + NMAX + 2][1 + NMAX + 2];
int main()
{
ifstream in("zoo.in");
ofstream out("zoo.out");
int n;
in >> n;
coordX.push_back(-2000000001);
coordX.push_back(2000000001);
coordY.push_back(-2000000001);
coordY.push_back(2000000001);
for (int i = 1; i <= n; i++)
{
int x, y;
in >> x >> y;
puncte.emplace_back(x, y);
coordX.push_back(x);
coordY.push_back(y);
}
sort(coordX.begin(), coordX.end());
sort(coordY.begin(), coordY.end());
for (int i = 0; i < coordX.size(); i++)
{
normX[coordX[i]] = i + 1;
}
for (int j = 0; j < coordY.size(); j++)
{
normY[coordY[j]] = j + 1;
}
for (int i = 0; i < puncte.size(); i++)
{
mat[normX[puncte[i].first]][normY[puncte[i].second]]++;
}
for (int i = 1; i <= n + 2; i++)
{
for (int j = 1; j <= n + 2; j++)
{
mat[i][j] = mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1] + mat[i][j];
}
}
int m;
in >> m;
int st;
int dr;
for (int j = 1; j <= m; j++)
{
int x1, y1, x2, y2;
in >> x1 >> y1 >> x2 >> y2;
st = 0;
dr = coordX.size() - 1;
int solX1 = coordX.size() - 1;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (coordX[mij] >= x1)
{
solX1 = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
st = 0;
dr = coordX.size() - 1;
int solX2 = 0;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (coordX[mij] <= x2)
{
solX2 = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
st = 0;
dr = coordY.size() - 1;
int solY1 = coordY.size() - 1;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (coordY[mij] >= y1)
{
solY1 = mij;
dr = mij - 1;
}
else
{
st = mij + 1;
}
}
st = 0;
dr = coordY.size() - 1;
int solY2 = 0;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (coordY[mij] <= y2)
{
solY2 = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
solX1++;
solY1++;
solX2++;
solY2++;
out << mat[solX2][solY2] - mat[solX2][solY1 - 1] - mat[solX1 - 1][solY2] + mat[solX1 - 1][solY1 - 1] << '\n';
}
return 0;
}