Pagini recente » Cod sursa (job #924873) | Cod sursa (job #474303) | Cod sursa (job #1687669) | Cod sursa (job #519762) | Cod sursa (job #2455996)
#include <bits/stdc++.h>
using namespace std;
ofstream fout("zoo.out");
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
const long long Bound = 2e9;
struct SegmentTree
{
long long l;
long long r;
vector <long long> v;
SegmentTree *st;
SegmentTree *dr;
SegmentTree()
{
st = nullptr;
dr = nullptr;
l = 0LL;
r = 0LL;
v.clear();
}
void Expand(int dir)
{
SegmentTree *now = this;
if(dir == 0)
{
if(now -> st == nullptr)
{
now -> st = new SegmentTree;
now -> st -> l = now -> l;
now -> st -> r = (now -> l + now -> r) / 2;
}
}
else
{
if(now -> dr == nullptr)
{
now -> dr = new SegmentTree;
now -> dr -> l = (now -> l + now -> r) / 2 + 1;
now -> dr -> r = now -> r;
}
}
}
void update(long long linie, long long col)
{
SegmentTree *now = this;
now -> v.push_back(col);
if(l == r)
{
return ;
}
long long mid = (now -> l + now -> r) / 2;
if(linie <= mid)
{
now -> Expand(0);
now -> st -> update(linie, col);
}
else
{
now -> Expand(1);
now -> dr -> update(linie, col);
}
}
int get(vector <long long> v, long long x, long long y)
{
if(v.size() == 0)
return 0;
int n = v.size();
int l = 0;
int r = n - 1;
int itr1 = 0;
int itr2 = 0;
if(v[r] < x)
return 0;
if(v[l] > y)
return 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(v[mid] < x)
{
l = mid + 1;
}
else
{
itr1 = mid;
r = mid - 1;
}
}
if(v[itr1] > y)
return 0;
l = 0;
r = n - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(v[mid] > y)
{
r = mid - 1;
}
else
{
l = mid + 1;
itr2 = mid;
}
}
if(v[itr2] < x)
return 0;
return itr2 - itr1 + 1;
}
int query(long long x1, long long y1, long long x2, long long y2)
{
SegmentTree *now = this;
long long l = now -> l;
long long r = now -> r;
if(x1 <= l && r <= x2)
{
return get(now -> v, y1, y2);
}
long long mid = (l + r) / 2;
int sum = 0;
if(x1 <= mid && now -> st != nullptr)
sum += now -> st -> query(x1, y1, x2, y2);
if(x2 > mid && now -> dr != nullptr)
sum += now -> dr -> query(x1, y1, x2, y2);
return sum;
}
void aranjare()
{
SegmentTree *now = this;
sort(now -> v.begin(), now -> v.end());
if(now -> st != nullptr)
now -> st -> aranjare();
if(now -> dr != nullptr)
now -> dr -> aranjare();
}
};
SegmentTree *arb = new SegmentTree;
void upd(long long &x)
{
x = x + Bound + 1;
}
main()
{
InParser fin("zoo.in");
arb -> l = 1LL;
arb -> r = Bound * 2 + 1;
int n;
fin >> n;
while(n--)
{
long long x, y;
fin >> x >> y;
upd(x);
upd(y);
arb -> update(x, y);
}
arb -> aranjare();
fin >> n;
while(n--)
{
long long x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
upd(x1);
upd(y1);
upd(x2);
upd(y2);
int p = arb -> query(x1, y1, x2, y2);
fout << p << '\n';
}
}