Pagini recente » Cod sursa (job #380039) | Cod sursa (job #2456087)
#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;
}
};
SegmentTree *arb = new SegmentTree;
struct Point
{
int x, y;
int pos;
};
vector <Point> t;
bool cmp1(Point x, Point y)
{
return x.x <= y.x;
}
bool cmp2(Point x, Point y)
{
return x.y <= y.y;
}
main()
{
InParser fin("zoo.in");
arb -> l = 1LL;
int n;
fin >> n;
while(n--)
{
long long x, y;
fin >> x >> y;
t.push_back({x, y, 0});
}
int k = 1;
sort(t.begin(), t.end(), cmp1);
t[0].pos = 1;
for(int i = 1; i < t.size(); i++)
{
if(t[i].x != t[i - 1].x)
k++;
t[i].pos = k;
}
arb -> r = k;
sort(t.begin(), t.end(), cmp2);
for(auto i : t)
arb -> update(i.pos, i.y);
sort(t.begin(), t.end(), cmp1);
fin >> n;
while(n--)
{
long long x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
int it1 = 0;
int it2 = 0;
int l = 0;
int r = t.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(t[mid].x < x1)
{
l = mid + 1;
}
else
{
r = mid - 1;
it1 = mid;
}
}
l = 0;
r = t.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(t[mid].x > x2)
{
r = mid - 1;
}
else
{
l = mid + 1;
it2 = mid;
}
}
if(t[it1].x > x2 || t[it2].x < x1)
{
fout << 0 << '\n';
continue;
}
x1 = t[it1].pos;
x2 = t[it2].pos;
int p = arb -> query(x1, y1, x2, y2);
fout << p << '\n';
}
}