Cod sursa(job #2462305)

Utilizator Coroian_DavidCoroian David Coroian_David Data 27 septembrie 2019 08:28:45
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.97 kb
#include <bits/stdc++.h>

#define MAX_N 16000

using namespace std;

int n;

struct coord
{
    int x, y;
};

coord v[MAX_N + 1];

int x[MAX_N + 1];
int y[MAX_N + 1];

int kx, ky;
int dx[MAX_N + 1];
int dy[MAX_N + 1];

vector <int> g[(MAX_N << 2) + 1];

ifstream f("zoo.in");

void readFile()
{
    f >> n;

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

void getDiff(int a[], int d[], int &k)
{
    k = 1;
    d[1] = a[1];
    for(int i = 2; i <= n; i ++)
    {
     //   cout << a[i] << " ";
        if(a[i] != a[i - 1])
            d[++ k] = a[i];
    }

  //  cout << "\n";

   // cout << k << "\n";
}

int cautBin(int a[], int n, int nr)
{
    int i = 0;
    int pas = 1 << 13;
    while(pas != 0)
    {
        if(i + pas <= n && a[i + pas] <= nr)
            i += pas;

        pas >>= 1;
    }

    return i;
}

int cautBin2(int a[], int n, int nr)
{
    int i = 0;
    int pas = 1 << 13;
    while(pas != 0)
    {
        if(i + pas <= n && a[i + pas] < nr)
            i += pas;

        pas >>= 1;
    }

    return i + 1;
}


void baga(int poz, int st, int dr, int a, int y)
{
    if(st == dr)
    {
        g[poz].push_back(y);

        return;
    }

    int mid = (st + dr) >> 1;

    if(a <= mid)
        baga(poz << 1, st, mid, a, y);

    else
        baga((poz << 1) + 1, mid + 1, dr, a, y);
}

void comb(int a, int b, int c)
{
    int i = 0, j = 0;

    while(i < g[b].size() && j < g[c].size())
    {
        if(g[b][i] < g[c][j])
        {
            g[a].push_back(g[b][i]);
            i ++;
        }

        else
        {
            g[a].push_back(g[c][j]);
            j ++;
        }
    }

    while(i < g[b].size())
    {
        g[a].push_back(g[b][i]);
        i ++;
    }

    while(j < g[c].size())
    {
        g[a].push_back(g[c][j]);
        j ++;
    }

   // cout << " DIM " << g[b].size() + g[c].size() << " = " << g[a].size() << "\n";
}

int done[MAX_N * 4 + 1];

void build(int poz, int st, int dr, int a)
{
    if(st == dr)
    {
        done[poz] = 1;
        return;
    }

    int mid = (st + dr) >> 1;

    if(a <= mid)
        build(poz << 1, st, mid, a);

    else
        build((poz << 1) + 1, mid + 1, dr, a);


   // cout << mid + 1 << " " << dr << "\n";

    if(mid + 1 <= dr && done[poz << 1] && done[(poz << 1) + 1] && done[poz] == 0)
        comb(poz, poz << 1, (poz << 1) + 1), done[poz] = 1;

    else if(mid + 1 > dr && done[poz << 1] && done[poz] == 0)
    {
        done[poz] = 1;
        for(auto u : g[poz << 1])
            g[poz].push_back(u);
    }

   // cout << " SUNTEM " << poz << " " << st << " " << dr << " " << a << " DONE " << done[poz] << "\n";

  /*  cout <<  "AVEM \n";
    for(auto u : g[poz])
        cout << u << " ";
    cout << "\n";*/

}

void solve()
{
    sort(x + 1, x + n + 1);
    sort(y + 1, y + n + 1);

    getDiff(x, dx, kx);
    getDiff(y, dy, ky);

    for(int i = 1; i <= n; i ++)
    {
        int px = cautBin(dx, kx, v[i].x);
        int py = cautBin(dy, ky, v[i].y);

        baga(1, 1, kx, px, py);
    }

  //  cout << "DAM NBUILD\n";
    for(int i = 1; i <= n; i ++)
        build(1, 1, kx, i);
}

int rez;

void getRez(int poz, int st, int dr, int a, int b, int y1, int y2)
{
    if(st == a && dr == b)
    {
        vector <int> :: iterator it = lower_bound(g[poz].begin(), g[poz].end(), y1);
        vector <int> :: iterator it2 = upper_bound(g[poz].begin(), g[poz].end(), y2);
        it2 --;
/*
        for(auto u : g[poz])
            cout << u << " " ;
        cout << "\n";*/

      //  cout << "PENTRU " << st << " " << dr << " " << " AVEM " << y1 << " " << y2 << " " << (it2 - it + 1) << "\n";

        if(it <= it2)
            rez += (it2 - it + 1);

        return;
    }

    int mid = (st + dr) >> 1;
    if(b <= mid)
        getRez(poz << 1, st, mid, a, b, y1, y2);

    if(a > mid)
        getRez((poz << 1) + 1, mid + 1, dr, a, b, y1, y2);

    if(a <= mid && b > mid)
    {
        getRez(poz << 1, st, mid, a, mid, y1, y2);
        getRez((poz << 1) + 1, mid + 1, dr, mid + 1, b, y1, y2);
    }
}

void ansQues()
{
    ofstream g("zoo.out");

    int q;
    f >> q;
    while(q > 0)
    {
        q --;
        int x1, y1, x2, y2;
        f >> x1 >> y1 >> x2 >> y2;

        if(x1 > dx[kx] || x2 < dx[1] || y1 > dy[ky] || y2 < dy[1])
        {
            g << "0\n";

            continue;
        }

        x1 = cautBin2(dx, kx, x1);
        x2 = cautBin(dx, kx, x2);
        y1 = cautBin2(dy, ky, y1);
        y2 = cautBin(dy, ky, y2);

    //    cout << " Q " << x1 << " " << y1 << " DREAPTA JOS " << x2 << " " << y2 << "\n";

        rez = 0;
        getRez(1, 1, kx, x1, x2, y1, y2);

        g << rez << "\n";
    }
}

int main()
{
    readFile();

    solve();

    ansQues();

    return 0;
}