Pagini recente » Cod sursa (job #2931032) | Cod sursa (job #683820) | Cod sursa (job #2286232) | Cod sursa (job #2570201) | Cod sursa (job #1759613)
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
ofstream fout( "zoo.out" );
class InputReader{
public:
InputReader() {}
InputReader(const char *name) {
fin = fopen(name, "r");
buffpos = Size - 1;
}
inline InputReader &operator >> (int &n) {
char x = nextpos();
while ((x < '0' || x > '9') && x != '-') x = nextpos();
int semn = 1;
if (x == '-') {
semn = -1; x = nextpos();
}
n = 0;
while (x >= '0' && x <= '9') {
n = n * 10 + x - '0';
x = nextpos();
}
n *= semn;
return *this;
}
private:
static const int Size = (1 << 17);
FILE *fin;
int buffpos;
char buff[ Size ];
inline char nextpos() {
++ buffpos;
if (buffpos == Size) {
fread(buff, Size, 1, fin);
buffpos = 0;
}
return buff[ buffpos ];
}
} fin ("zoo.in");
const int nmax = 16000;
const int mmax = 1e5;
const int cate_val = 4 * mmax + nmax + 1;
int n, m, nrm;
int solutie[mmax + 1];
struct pct{
int ind, x, y, semn;
pct() {}
pct (int _ind, int _x, int _y, int _semn) {
ind = _ind, x = _x, y = _y, semn = _semn;
}
inline bool operator < (const pct &a) const {
if (x != a.x) return (x < a.x);
if (ind != a.ind) return (ind < a.ind);
return (y < a.y);
}
} q[4 * mmax + nmax + 1];
class Aib{
public:
int aib[cate_val + 1];
void update (int pos, int val) {
for (int i = pos; i <= cate_val; i += lsb( i )) {
aib[ i ] += val;
}
}
inline int query (int pos) {
int ans = 0;
for (int i = pos; i > 0; i -= lsb( i )) {
ans += aib[ i ];
}
return ans;
}
private:
inline int lsb (int x) {
return x & -x;
}
} aib;
typedef map <int, int> mii;
mii auxx, auxy;
void prelucrare_date() {
for (int i = 1; i <= nrm; ++ i) {
auxx[ q[ i ].x ] = 0, auxy[ q[ i ].y ] = 0;
}
int ind = 1;
for (mii::iterator it = auxx.begin(); it != auxx.end(); ++ it, ++ ind) {
it -> second = ind;
}
ind = 1;
for (mii::iterator it = auxy.begin(); it != auxy.end(); ++ it, ++ ind) {
it -> second = ind;
}
for (int i = 1; i <= nrm; ++ i) {
q[ i ].x = auxx[ q[ i ].x ], q[ i ].y = auxy[ q[ i ].y ];
}
auxx.clear(), auxy.clear();
}
void rezolva() {
sort(q + 1, q + nrm + 1);
for (int i = 1; i <= nrm; ++ i) {
if (q[ i ].ind == 0) {
aib.update(q[ i ].y, 1);
} else {
solutie[ q[ i ].ind ] += q[ i ].semn * aib.query( q[ i ].y );
}
}
}
int main() {
fin >> n;
nrm = 0;
for (int i = 1; i <= n; ++ i) {
int x, y;
fin >> x >> y;
q[ ++ nrm ] = pct(0, x, y, 0);
}
fin >> m;
for (int i = 1; i <= m; ++ i) {
int x, y, xx, yy;
fin >> x >> y >> xx >> yy;
q[ ++ nrm ] = pct(i, xx, yy, 1);
q[ ++ nrm ] = pct(i, xx, y - 1, -1);
q[ ++ nrm ] = pct(i, x - 1, yy, -1);
q[ ++ nrm ] = pct(i, x - 1, y - 1, 1);
}
prelucrare_date();
rezolva();
for (int i = 1; i <= m; ++ i) {
fout << solutie[ i ] << "\n";
}
fout.close();
return 0;
}