Nu aveti permisiuni pentru a descarca fisierul grader_test12.in
Cod sursa(job #3161514)
Utilizator | Data | 27 octombrie 2023 13:02:01 | |
---|---|---|---|
Problema | Zoo | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 2.89 kb |
#include <fstream>
#include <algorithm>
#include <vector>
#define sz 26000
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
pair<int,int> pp[sz + 5];
vector <int> a[sz * 4 + 5];
vector <int> el[sz + 5];
int vk[sz + 5];
int k;
int k2;
int n;
int q;
void interclass(vector<int>& a,vector<int>& b,vector<int>& c)
{
int i=0;
int j=0;
int sza = a.size();
int szb = b.size();
c.reserve(sza+szb+1);
while(i<sza && j<szb)
{
if(a[i] < b[j])
c.push_back(a[i]),i++;
else
c.push_back(b[j]),j++;
}
while(i<sza)
c.push_back(a[i]),i++;
while(j<szb)
c.push_back(a[j]),j++;
}
void build(int nod,int st,int dr)
{
if(st==dr)
{
a[nod] = el[st];
return;
}
int mid = (st+dr)/2;
build(nod*2,st,mid);
build(nod*2+1,mid+1,dr);
interclass(a[nod*2],a[nod*2+1],a[nod]);
}
int query(int nod,int st,int dr,int x,int y,int x2,int y2)
{
if(x<=st && dr<=x2)
return upper_bound(a[nod].begin(),a[nod].end(),y2) - lower_bound(a[nod].begin(),a[nod].end(),y);
int mid = (st+dr)/2;
if(x>mid)
return query(nod*2+1,mid+1,dr,x,y,x2,y2);
if(x2<=mid)
return query(nod*2,st,mid,x,y,x2,y2);
return query(nod*2,st,mid,x,y,x2,y2) + query(nod*2+1,mid+1,dr,x,y,x2,y2);
}
int cb(int val)
{
int st =1;
int dr = k2;
int p = 0;
while(st<=dr)
{
int mid = (st+dr)/2;
if ( val < vk[mid])
dr=mid-1;
else if ( val > vk[mid])
st=mid+1;
else{
return mid;
}
}
return p;
}
int left_border(int x)
{
int st=1;
int dr=k2;
int p = k2 + 1;
while(st<=dr)
{
int mid = (st+dr)/2;
if (vk[mid] < x)
st=mid+1;
else
p=min(p,mid),dr=mid-1;
}
return p;
}
int right_border(int x)
{
int st=1;
int dr=k2;
int p=0;
while(st<=dr)
{
int mid = (st+dr)/2;
if(vk[mid] > x)
dr=mid-1;
else
p=max(p,mid),st=mid+1;
}
return p;
}
int main()
{
fin>>n;
for(int i =1 ;i<=n;i++)
{
fin>>pp[i].first>>pp[i].second;
vk[++k] = pp[i].first;
}
sort(vk+1,vk+k+1);
k2=1;
for(int i = 2; i<=k;i++)
if(vk[i]!=vk[i-1])
vk[++k2]=vk[i];
for(int i =1;i<=n;i++){
pp[i].first = cb(pp[i].first);
el[pp[i].first].push_back(pp[i].second);
}
build(1,1,k2);
fin>>q;
for(int i=1;i<=q;i++)
{
int x,y,x2,y2;
fin>>x>>y>>x2>>y2;
int rx = left_border(x);
int rx2 = right_border(x2);
if(rx > rx2)
fout<<0<<'\n';
else
fout<<query(1,1,k2,rx,y,rx2,y2)<<'\n';
}
}