Cod sursa(job #3303861)

Utilizator Victor5539Tanase Victor Victor5539 Data 18 iulie 2025 15:52:09
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define pb push_back
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int NMAX=16000;
int q;
short n,i,y_size,x_size,cnt,sol;
vector <short> A[4*NMAX+5],p[NMAX+5];
vector <int> x,y;

struct point{
int x,y;
short idx_x,idx_y;}v[NMAX+5];

bool compare(point a, point b)
{
    if (a.x!=b.x)
        return a.x<b.x;

    if (a.y!=b.y)
        return a.y<b.y;
}

bool compare2(point a, point b)
{
    if (a.y!=b.y)
        return a.y<b.y;
}


void build(int nod ,short st ,short dr)
{
    if (st==dr)
    {
        for (auto y: p[st])
            A[nod].pb(y);
    }
    else
    {
        short mij=(st+dr)>>1;
        build(2*nod,st,mij);
        build(2*nod+1,mij+1,dr);

        short i=0,j=0;

        while (i<A[2*nod].size() && j<A[2*nod+1].size())
        {
            if (A[2*nod][i]<A[2*nod+1][j])
            {
                A[nod].pb(A[2*nod][i]);
                i++;
            }
            else
            {
                A[nod].pb(A[2*nod+1][j]);
                j++;
            }
        }

        while (i<A[2*nod].size())
        {
            A[nod].pb(A[2*nod][i]);
            i++;
        }

        while (j<A[2*nod+1].size())
        {
            A[nod].pb(A[2*nod+1][j]);
            j++;
        }
    }
}

void query(int nod, short st , short dr , short a, short b, short y1 ,short y2)
{
    if (a<=st && dr<=b)
        sol+=lower_bound(A[nod].begin(),A[nod].end(),y2)-upper_bound(A[nod].begin(),A[nod].end(),y1);
    else
    {
        int mij=(st+dr)>>1;

        if (a<=mij)
            query(2*nod,st,mij,a,b,y1,y2);

        if (b>mij)
            query(2*nod+1,mij+1,dr,a,b,y1,y2);
    }
}

int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].x>>v[i].y;

    v[0].x=v[0].y=-2e9-1;

    sort(v+1,v+n+1,compare2);

    for (i=1; i<=n; i++)
    {
        if (v[i].y!=v[i-1].y)
        {
            y_size++;
            y.pb(v[i].y);
        }

        v[i].idx_y=y_size;
    }

    sort(v+1,v+n+1,compare);

    for (i=1; i<=n; i++)
    {
        if (v[i].x!=v[i-1].x)
        {
            x_size++;
            x.pb(v[i].x);
        }

        p[x_size].pb(v[i].idx_y);
    }

    build(1,1,x_size);


    return 0;
}