Cod sursa(job #1166078)

Utilizator stefanzzzStefan Popa stefanzzz Data 3 aprilie 2014 10:57:24
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define MAXN 16005
#define MAXC 100
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");

int n,m,cnt,x,x11,x22,y11,y22,sol;
pair<int,int> pct[MAXN];
set<int> sx;
set<int>::iterator it;
vector<int> vx,pctx[MAXN],ai[4*MAXN];
char s[MAXC];

inline void build_ai(int nod,int st,int dr);
inline void query_ai(int nod,int st,int dr);
inline int get_int(){
    int semn;
    if(s[cnt]=='-'){
        semn=-1;
        cnt++;}
    else
        semn=1;
    x=s[cnt++]-'0';
    while(s[cnt]>='0'&&s[cnt]<='9')
        x=x*10+s[cnt++]-'0';
    cnt++;
    return semn*x;}

int main()
{
    int i;
    f>>n;
    f.getline(s,MAXC,'\n');
    for(i=1;i<=n;i++){
        f.getline(s,MAXC,'\n');
        cnt=0;
        pct[i].first=get_int();
        pct[i].second=get_int();
        sx.insert(pct[i].first);}
    for(it=sx.begin();it!=sx.end();it++)
        vx.push_back(*it);
    for(i=1;i<=n;i++){
        pct[i].first=(lower_bound(vx.begin(),vx.end(),pct[i].first)-vx.begin())+1;
        pctx[pct[i].first].push_back(pct[i].second);}
    n=vx.size();
    for(i=1;i<=n;i++)
        sort(pctx[i].begin(),pctx[i].end());
    build_ai(1,1,n);
    f>>m;
    f.getline(s,MAXC,'\n');
    for(i=1;i<=m;i++){
        f.getline(s,MAXC,'\n');
        cnt=0;
        x11=get_int();y11=get_int();
        x22=get_int();y22=get_int();
        sol=0;
        x11=(lower_bound(vx.begin(),vx.end(),x11)-vx.begin())+1;
        x22=upper_bound(vx.begin(),vx.end(),x22)-vx.begin();
        if(x11>n||!x22){
            g<<"0\n";
            continue;}
        query_ai(1,1,n);
        g<<sol<<'\n';}
    f.close();
    g.close();
    return 0;
}

inline void build_ai(int nod,int st,int dr){
    int i,j,mij;
    if(st==dr){
        for(i=0;i<pctx[st].size();i++)
            ai[nod].push_back(pctx[st][i]);
        return;}
    mij=(st+dr)>>1;
    build_ai(2*nod,st,mij);
    build_ai(2*nod+1,mij+1,dr);
    for(i=0,j=0;i<ai[2*nod].size()||j<ai[2*nod+1].size();){
        if(i<ai[2*nod].size()&&(j==ai[2*nod+1].size()||ai[2*nod][i]<ai[2*nod+1][j])){
            ai[nod].push_back(ai[2*nod][i]);
            i++;}
        else{
            ai[nod].push_back(ai[2*nod+1][j]);
            j++;}}}

inline void query_ai(int nod,int st,int dr){
    if(st>=x11&&dr<=x22){
        x=upper_bound(ai[nod].begin(),ai[nod].end(),y22)-lower_bound(ai[nod].begin(),ai[nod].end(),y11);
        if(x>0)
            sol+=x;
        return;}
    int mij;
    mij=(st+dr)>>1;
    if(x11<=mij)
        query_ai(2*nod,st,mij);
    if(x22>mij)
        query_ai(2*nod+1,mij+1,dr);}