Cod sursa(job #2501366)

Utilizator bogdi1bogdan bancuta bogdi1 Data 29 noiembrie 2019 16:42:33
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.31 kb
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <ctype.h>
using namespace std;
const int INF = 1000000000;
vector<int> arbint[864005];
map<int,int> mp;
vector<int> puncte[216005];
struct Oite
{
    int x,y;
} oi[16005];
struct Drept
{
    int x1,y1,x2,y2;
} que[100005];
int nn;
/** Funcţiile necesare parsării fişierului de intrare **/
FILE *_fin, *fout;
int _in_loc; char _in_buff[4096];


void read_init(const char* nume) // Apelaţi această funcţie la începutul funcţiei <main>
{
	_fin = fopen(nume, "r");
	_in_loc = 4095;
}

char read_ch()
{
	++_in_loc;
	if (_in_loc == 4096) {
		_in_loc = 0;
		fread(_in_buff, 1, 4096, _fin);
	}
	return _in_buff[_in_loc];
}

int read_u32() // Apelaţi această funcţie pentru a citi un număr ce se încadrează în categoria <unsigned int>
{
	int u32 = 0; char c;
	while (!isdigit(c = read_ch()) && c != '-');
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
	} else {
		u32 = c - '0';
	}
	while (isdigit(c = read_ch())) {
		u32 = u32 * 10 + c - '0';
	}
	return u32 * sgn;
}
inline int bsf(int ind, int val)
{
    int st=0,dr=arbint[ind].size()-1,med,last=INF;
    while(st<=dr){
        med=(st+dr)/2;
        if(arbint[ind][med]>=val){
            last=med;
            dr=med-1;
        }
        else
            st=med+1;
    }
    return last;
}
inline int bsl(int ind, int val)
{
    int st=0,dr=arbint[ind].size()-1,med,last=-INF;
    while(st<=dr){
        med=(st+dr)/2;
        if(arbint[ind][med]<=val){
            st=med+1;
            last=med;
        }
        else
            dr=med-1;
    }
    return last;
}
void create(int nod, int value)
{
    for(int i=0; i<puncte[value].size(); i++)
        arbint[nod].push_back(puncte[value][i]);
}
void join(int nod, int left, int right)
{
    int i=0,j=0;
    while(i<arbint[left].size() && j<arbint[right].size()){
        if(arbint[left][i]<arbint[right][j]){
            arbint[nod].push_back(arbint[left][i]);
            i++;
        }
        else{
            arbint[nod].push_back(arbint[right][j]);
            j++;
        }
    }
    while(i<arbint[left].size()){
        arbint[nod].push_back(arbint[left][i]);
        i++;
    }
    while(j<arbint[right].size()){
        arbint[nod].push_back(arbint[right][j]);
        j++;
    }
}
void build(int nod, int st, int dr)
{
    if(st==dr)
        create(nod, st);
    else{
        int mij=(st+dr)/2;
        build(2*nod, st, mij);
        build(2*nod+1, mij+1, dr);
        join(nod, 2*nod, 2*nod+1);
    }
}
void build()
{
    build(1, 1, nn);
}
int query(int nod, int st, int dr, int left, int right, int ymin, int ymax)
{
    if(st==left && dr==right){
        int x=bsf(nod, ymin);
        int y=bsl(nod, ymax);
        return max(0, y-x+1);
    }
    else{
        int mij=(st+dr)/2;
        if(right<=mij)
            return query(2*nod, st, mij, left, right, ymin, ymax);
        else{
            if(mij<left)
                return query(2*nod+1, mij+1, dr, left, right, ymin, ymax);
            else
                return query(2*nod, st, mij, left, mij, ymin, ymax)+query(2*nod+1, mij+1, dr, mij+1, right, ymin, ymax);
        }
    }
}
int query(int left, int right, int ymin, int ymax)
{
    return query(1, 1, nn, left, right, ymin, ymax);
}
int main()
{
    fout=fopen("zoo.out", "w");
    int n,m,i;
    read_init("zoo.in");
    n=read_u32();
    for(i=1; i<=n; i++){
        oi[i].x=read_u32();
        oi[i].y=read_u32();
        mp[oi[i].x];
    }
    m=read_u32();
    for(i=1; i<=m; i++){
        que[i].x1=read_u32();
        que[i].y1=read_u32();
        que[i].x2=read_u32();
        que[i].y2=read_u32();
        mp[que[i].x1];
        mp[que[i].x2];
    }
    map<int, int>::iterator it;
    map<int,int>::iterator it1;
    for(it=mp.begin(), i=1; it!=mp.end(); it++,i++)
        it->second=i;
    nn=i-1;
    for(i=1; i<=n; i++){
        it=mp.find(oi[i].x);
        puncte[it->second].push_back(oi[i].y);
    }
    for(i=1; i<=nn; i++)
        sort(puncte[i].begin(), puncte[i].end());
    build();
    for(i=1; i<=m; i++){
        it=mp.find(que[i].x1);
        it1=mp.find(que[i].x2);
        fprintf(fout, "%d\n", query(it->second, it1->second, que[i].y1, que[i].y2));
    }
    return 0;
}