Cod sursa(job #1473235)

Utilizator MaligMamaliga cu smantana Malig Data 18 august 2015 21:02:35
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 12.85 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,M;

struct punct {
    int x,y;
}v[16010];

struct elem {
    int* vect;
}arb[524288];

bool cmp(punct,punct);
void formeaza_arb(int,int,int);
int query(int,int,int,int,int,int,int);
int binary_s(int*,int,int);

int main()
{
    f>>N;
    FOR (i,1,N) {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+N+1,cmp);
    /*FOR (i,1,N) {
        g<<v[i].x<<' '<<v[i].y<<'\n';
    }
    g<<'\n';*/
    formeaza_arb(1,1,N);
    /*int x=3;
    FOR (i,1,5) {
        g<<arb[x].vect[i]<<'\n';
    }
    g<<"\n\n";*/
    f>>M;
    FOR (i,1,M) {
        int x1,y1,x2,y2;
        f>>x1>>y1>>x2>>y2;
        g<<query(1,1,N,x1,y1,x2,y2)<<'\n';
    }
    f.close();g.close();
    return 0;
}

bool cmp(punct a,punct b) {
    return a.x<b.x;
}

void formeaza_arb(int nod,int st,int dr) {
    //cout<<nod<<' '<<st<<' '<<dr<<'\n';
    arb[nod].vect=new int[dr-st+2];
    if (st==dr) {
        arb[nod].vect[1]=v[st].y;
        //cout<<nod<<' '<<st<<' '<<dr<<' '<<v[st].x<<' '<<v[st].y<<'\n';
    }
    else {
        int mij=(st+dr)>>1;
        formeaza_arb((nod<<1),st,mij);
        formeaza_arb((nod<<1)+1,mij+1,dr);
        int limst,limdr;
        limst=mij-st+1;
        limdr=dr-(mij+1)+1;
        int i=1,j=1,dimvect=0;
        while (i<=limst && j<=limdr) {
            if (arb[(nod<<1)].vect[i]<arb[(nod<<1)+1].vect[j]) {
                arb[nod].vect[++dimvect]=arb[(nod<<1)].vect[i];
                ++i;
            }
            else {
                arb[nod].vect[++dimvect]=arb[(nod<<1)+1].vect[j];
                ++j;
            }
        }
        while (i<=limst) {
            arb[nod].vect[++dimvect]=arb[(nod<<1)].vect[i];
            ++i;
        }
        while (j<=limdr) {
            arb[nod].vect[++dimvect]=arb[(nod<<1)+1].vect[j];
            ++j;
        }
        /*cout<<nod<<'\n';
        FOR(i,1,dimvect) {
            cout<<arb[nod].vect[i].x<<' '<<arb[nod].vect[i].y<<'\n';
        }
        cout<<'\n';*/
    }
}

int query(int nod,int st,int dr,int x1,int y1,int x2,int y2) {
    //cout<<nod<<' '<<st<<' '<<dr<<'\n';
    if (x1<=v[st].x && v[dr].x<=x2) {
        int pozst,pozdr;
        pozst=binary_s(arb[nod].vect,dr-st+1,y1);
        pozdr=binary_s(arb[nod].vect,dr-st+1,y2);
        while (arb[nod].vect[pozst]<y1) {
            ++pozst;
        }
        while (arb[nod].vect[pozst-1]==arb[nod].vect[pozst]) {
            --pozst;
        }
        while (arb[nod].vect[pozdr]>y2) {
            --pozdr;
        }
        while (arb[nod].vect[pozdr+1]==arb[nod].vect[pozdr]) {
            ++pozdr;
        }
        //cout<<pozdr<<' '<<pozst<<'\n';
        return pozdr-pozst+1;
    }
    else if (st==dr) {
        return 0;
    }
    else {
        int mij=(st+dr)>>1;
        int rez=0;
        if (x1<=v[mij].x) {
            rez+=query((nod<<1),st,mij,x1,y1,x2,y2);
        }
        if (v[mij].x<x2) {
            rez+=query((nod<<1)+1,mij+1,dr,x1,y1,x2,y2);
        }
        return rez;
    }
}

int binary_s(int* vect,int dim,int val) {
    int st=1,dr=dim;
    while (st<dr) {
        int mij=(st+dr)>>1;
        if (val<vect[mij]) {
            dr=mij-1;
        }
        else if (val>vect[mij]) {
            st=mij+1;
        }
        else {
            return mij;
        }
    }
    return st;
}
/*#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,M;

struct punct {
    int x,y;
}v[16010];

struct item {
    punct elem;
    item* next=NULL;
};
struct lista {
    item *left,*right;
};
lista arb[16390];

struct idekam{
    int* vect;
}ca[16390];

bool cmp(punct,punct);
void formeaza_arb(int,int,int);
int query(int,int,int,int,int,int,int);

int main()
{
    f>>N;
    FOR (i,1,N) {
        f>>v[i].x>>v[i].y;
    }
    sort(v+1,v+N+1,cmp);
    FOR (i,1,N) {
        g<<v[i].x<<' '<<v[i].y<<'\n';
    }
    g<<'\n';
    formeaza_arb(1,1,N);
    item* p=arb[1].left;
    while (p->next!=NULL) {
        g<<p->elem.x<<' '<<p->elem.y<<'\n';
        p=p->next;
    }
    FOR (i,1,M) {
        int x1,y1,x2,y2;
        f>>x1>>y1>>x2>>y2;
        g<<query(1,1,N,x1,y1,x2,y2)<<'\n';
    }
    f.close();g.close();
    return 0;
}

bool cmp(punct a,punct b) {
    return a.x<b.x;
}

void formeaza_arb(int nod,int st,int dr) {
    ca[nod].vect=new int[dr-st+1];
    cout<<ca[nod].vect[dr-st];
    arb[nod].left=arb[nod].right=new item;
    //cout<<st<<' '<<dr<<'\n';
    if (st==dr) {
        item* p=new item;
        arb[nod].right->elem.x=v[st].x;
        arb[nod].right->elem.y=v[st].y;
        arb[nod].right->next=p;
        arb[nod].right=p;
    }
    else {
        int mij=(st+dr)>>1;
        formeaza_arb((nod<<1),st,mij);
        formeaza_arb((nod<<1)+1,mij+1,dr);
        item* stanga=arb[(nod<<1)].left;
        item* dreapta=arb[(nod<<1)+1].left;
        while (stanga->next!=NULL && dreapta->next!=NULL) {
            if ((stanga->elem.y)<(dreapta->elem.y)) {
                item* p=new item;
                arb[nod].right->elem=stanga->elem;
                arb[nod].right->next=p;
                arb[nod].right=p;
                stanga=stanga->next;
                cout<<'s';
            }
            else {
                item* p=new item;
                arb[nod].right->elem=dreapta->elem;
                arb[nod].right->next=p;
                arb[nod].right=p;
                dreapta=dreapta->next;
                cout<<'d';
            }
        }
        while (stanga->next!=NULL) {
            item* p=new item;
            arb[nod].right->elem=stanga->elem;
            arb[nod].right->next=p;
            arb[nod].right=p;
            stanga=stanga->next;
            cout<<'s';
        }
        while (dreapta->next!=NULL) {
            item* p=new item;
            arb[nod].right->elem=dreapta->elem;
            arb[nod].right->next=p;
            arb[nod].right=p;
            dreapta=dreapta->next;
            cout<<'d';
        }
    }
    cout<<'\n'<<nod<<' '<<st<<' '<<dr;
    cout<<"\n\n";
}

int query(int nod,int st,int dr,int x1,int y1,int x2,int y2) {
    if (x1<=v[st].x && v[dr].x<=x2) {

    }
    else {
        int mij=(st+dr)>>1,rez=0;
        if (x1<=mij) {
            rez+=query((nod<<1),st,mij,x1,y1,x2,y2);
        }
        if (mij<x2) {
            rez+=query((nod<<1)+1,mij+1,dr,x1,y1,x2,y2);
        }
    }
}
*/

/*#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 2000000100

using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int N,dimv,M,nrpat,dimlast;
int arb[16390];
int rez[100010];
int last[100010];
vector<int> puncte_pat[100010];
bitset<100010> verif;

struct pct {
    int x,y;
}punct[16010];

struct elem {
    bool e_punct=true;
    int x=0,y=0,poz=0,pozorig=0;
}v[116010];

struct pat {
    int x1,y1,x2,y2,pozorig=0;
}patrat[100010];

bool compar_patrat(pat,pat);
bool compar_punct(pct,pct);
bool cmp(elem,elem);
int binsearch(int);
void update(int,int,int,int,int,int);
int query(int,int,int,int,int);

int main()
{
    f>>N;
    FOR (i,1,N) {
        int x,y;
        f>>x>>y;
        punct[i].x=x;
        punct[i].y=y;
    }
    sort (punct+1,punct+N+1,compar_punct);
    FOR (i,1,N) {
        //g<<punct[i].x<<' '<<punct[i].y<<'\n';
        v[++dimv].x=punct[i].x;
        v[dimv].y=punct[i].y;
        v[dimv].poz=i;
    }
    f>>M;
    FOR (i,1,M) {
        int x1,x2,y1,y2;
        f>>x1>>y1>>x2>>y2;
        patrat[i].x1=x1;
        patrat[i].y1=y1;
        patrat[i].x2=x2;
        patrat[i].y2=y2;
        patrat[i].pozorig=i;
    }
    patrat[M+1].x1=patrat[M+1].y1=inf;
    sort (patrat+1,patrat+M+2,compar_patrat);
    FOR (i,1,M) {
        g<<patrat[i].x1<<' '<<patrat[i].y1<<' '<<patrat[i].x2<<' '<<patrat[i].y2<<' '<<'\n';
    }
    FOR (i,1,M) {
        v[++dimv].e_punct=false;
        v[dimv].x=patrat[i].x1;
        v[dimv].y=patrat[i].y1;
        v[dimv].poz=i;
        v[dimv].pozorig=patrat[i].pozorig;
        v[++dimv].e_punct=false;
        v[dimv].x=patrat[i].x2;
        v[dimv].y=patrat[i].y2;
        v[dimv].poz=i;
        v[dimv].pozorig=patrat[i].pozorig;
    }
    sort(v+1,v+dimv+1,cmp);
    FOR (i,1,dimv) {
        cout<<v[i].e_punct<<' '<<v[i].x<<' '<<v[i].y<<'\n';
        if (v[i].e_punct && nrpat) {
            int poz=v[i].poz;
            puncte_pat[last[dimlast]].pb(poz);
            update(1,1,N,poz,poz,1);
        }
        else if (!v[i].e_punct) {
            if (!verif.test(v[i].poz)) {
                verif.set(v[i].poz,1);
                ++nrpat;
                last[++dimlast]=v[i].poz;
            }
            else {
                verif.set(v[i].poz,0);
                --nrpat;
                int left,right;
                left=binsearch(patrat[v[i].poz].y1);
                while (punct[left].y<patrat[v[i].poz].y1) {
                    ++left;
                }
                while (punct[left-1].y==patrat[v[i].poz].y1) {
                    --left;
                }
                right=binsearch(patrat[v[i].poz].y2);
                while (punct[right].y>patrat[v[i].poz].y2) {
                    --right;
                }
                while (punct[right+1].y==patrat[v[i].poz].y2) {
                    ++right;
                }
                rez[v[i].pozorig]=query(1,1,N,left,right);
                if (!nrpat) {
                    update(1,1,N,1,N,0);
                }
                else if (v[i].poz==last[1]) {
                    for (unsigned int k=0;k<puncte_pat[last[1]].size();++k) {
                        update(1,1,N,puncte_pat[last[1]][k],puncte_pat[last[1]][k],0);
                    }
                }
                if (v[i].poz==last[dimlast]) {
                    --dimlast;
                }
            }
        }
    }
    FOR (i,1,M) {
        g<<rez[i]<<'\n';
    }
    f.close();g.close();
    return 0;
}

int binsearch(int val) {
    int left=1,right=N;
    while (left<right) {
        int mij=(left+right)>>1;
        if (punct[mij].y==val) {
            return mij;
        }
        else if (val<punct[mij].y) {
            right=mij-1;
        }
        else {
            left=mij+1;
        }
    }
    return left;
}

void update(int nod,int st,int dr,int a,int b,int val) {
    if (a<=st && dr<=b) {
        if (val==1) {
            arb[nod]=dr-st+1;
        }
        else {
            arb[nod]=0;
        }
    }
    else {
        int mij=(st+dr)>>1;
        if (arb[nod]==0) {
            arb[(nod<<1)]=arb[(nod<<1)+1]=0;
        }
        else if (arb[nod]==dr-st+1) {
            arb[(nod<<1)]=mij-st+1;
            arb[(nod<<1)+1]=dr-(mij+1)+1;
        }
        if (a<=mij) {
            update((nod<<1),st,mij,a,b,val);
        }
        if (mij<b) {
            update((nod<<1)+1,mij+1,dr,a,b,val);
        }
        arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
    }
}

int query(int nod,int st,int dr,int a,int b) {
    if (a<=st && dr<=b) {
        return arb[nod];
    }
    else {
        int mij=(st+dr)>>1;
        if (arb[nod]==0) {
            arb[(nod<<1)]=arb[(nod<<1)+1]=0;
        }
        else if (arb[nod]==dr-st+1) {
            arb[(nod<<1)]=mij-st+1;
            arb[(nod<<1)+1]=dr-(mij+1)+1;
        }
        int rez=0;
        if (a<=mij) {
            rez+=query((nod<<1),st,mij,a,b);
        }
        if (mij<b) {
            rez+=query((nod<<1)+1,mij+1,dr,a,b);
        }
        arb[nod]=arb[(nod<<1)]+arb[(nod<<1)+1];
        return rez;
    }
}

bool compar_patrat(pat a,pat b) {
    if (a.x1!=b.x1) {
        return a.x1<b.x1;
    }
    else {
        return a.y1<b.y1;
    }
}

bool compar_punct(pct a,pct b) {
    return a.y<b.y;
}

bool cmp(elem a,elem b) {
    if (a.x!=b.x) {
        return a.x<b.x;
    }
    else {
        if (!a.e_punct) {
            return true;
        }
        else {
            return false;
        }
    }
}


*/