Nu aveti permisiuni pentru a descarca fisierul grader_test32.in
Cod sursa(job #6736)
Utilizator | Data | 20 ianuarie 2007 19:29:53 | |
---|---|---|---|
Problema | Zoo | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 3.6 kb |
#include <cstdio>
#include <algorithm>
#include <vector>
#define Nmax 16384
#define x first
#define y second
#define pb push_back
#define sz(a) int((a).size())
using namespace std;
int n, m, i, j, a, b, vl, x1, y1, x2, y2, mem;
pair<int,int> punct[Nmax];
vector<int> l[Nmax*2];
void update(int nod, int st, int dr)
{
if (a <= st && dr <= b)
{
l[nod].pb(vl);
}
else
{
int mij = (st + dr) >> 1;
if (a <= mij)
update(nod << 1, st, mij);
if (mij < b)
update((nod << 1) + 1, mij + 1, dr);
}
}
void interclaseaza(int nod)
{
int ind1 = 0, ind2 = 0, i;
int nod1 = nod << 1, nod2 = (nod << 1) + 1;
l[nod].resize(sz(l[nod1]) + sz(l[nod2]));
for (i=1; i<=sz(l[nod1]) + sz(l[nod2]); ++i)
{
if (ind1 < sz(l[nod1]) && ind2 < sz(l[nod2]))
if (l[nod1][ind1] < l[nod2][ind2])
{
l[nod][i-1] = (l[nod1][ind1]);
++ind1;
}
else
{
l[nod][i-1] = (l[nod2][ind2]);
++ind2;
}
else
if (ind1 == sz(l[nod1]))
{
l[nod][i-1] = (l[nod2][ind2]);
++ind2;
}
else
{
l[nod][i-1] = (l[nod1][ind1]);
++ind1;
}
}
}
void ord(int nod, int st, int dr)
{
if (st < dr)
{
int mij = (st + dr) >> 1;
ord(nod << 1, st, mij);
ord((nod << 1) + 1, mij + 1, dr);
interclaseaza(nod);
}
}
void solve()
{
sort(punct+1, punct+n+1);
for (i=1; i<=n; ++i)
{
a = b = i;
vl = punct[i].y;
update(1,1,n);
}
ord(1,1,n);
}
int cauta(int nod)
{
//printf("nod %d\n", nod);
//int st,dr,mij,v1 = -1,v2 = -1;
return 0;
if (sz(l[nod]) == 0)
return 0;
/*
st = 0;
dr = sz(l[nod])-1;
while (st <= dr)
{
mij = (st + dr) >> 1;
if (y1 <= l[nod][mij])
{
v1 = mij;
dr = mij - 1;
}
else
st = mij + 1;
}
//printf("v1 %d\n",v1);
st = 0;
dr = sz(l[nod])-1;
while (st <= dr)
{
mij = (st + dr) >> 1;
if (y2 >= l[nod][mij])
{
v2 = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
//printf("v2 %d\n", v2);
if (v1 != -1 && v2 != -1)
return v2 - v1 + 1;
return 0;
*/
}
int query(int nod, int st, int dr)
{
if (x1 <= punct[st].x && punct[dr].x <= x2)
{
return cauta(nod);
}
else
{
int mij = (st + dr) >> 1, ret = 0;
if (x1 <= punct[mij].x)
ret += query(nod << 1, st, mij);
if (punct[mij+1].x <= x2)
ret += query((nod << 1) + 1, mij + 1, dr);
return ret;
}
}
void solvequery()
{
scanf("%d\n", &m);
for (i=1; i<=m; ++i)
{
scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
printf("%d\n", query(1,1,n));
}
//printf("\n");
//for (i=0; i<sz(l[1]); ++i)
// printf("%d ", l[1][i]);
}
void citire()
{
scanf("%d\n", &n);
for (i=1; i<=n; ++i)
scanf("%d %d\n", &punct[i].x, &punct[i].y);
solve();
solvequery();
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
citire();
/*
for (i=0; i<Nmax * 2; ++i)
mem += sz(l[i]);
printf("memorie: %d\n", mem);*/
return 0;
}