Cod sursa(job #2463027)

Utilizator Coroian_DavidCoroian David Coroian_David Data 28 septembrie 2019 10:30:31
Problema Zoo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 9.64 kb
#include <bits/stdc++.h>

#define MAX_N 16000
#define MAX_Q 100000

using namespace std;

typedef long long lint;

const lint MAX = (lint)(1e9) * 2;

const int DEBUG = 0;
const int N = 16000;

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");

int getNr()
{
    lint nr = 1LL * rand() * rand() % MAX;

    if(rand() & 1)
        nr *= (-1);

    return nr;
}

void readFile()
{
    srand(time(0));

    if(DEBUG)
    {
        n = N;
        for(int i = 1; i <= n; i ++)
        {
            //lint nr = 1LL * rand() * rand() % MAX;
            v[i].x = getNr();
           // nr = 1LL * rand() * rand() % MAX;
            v[i].y = getNr();
            x[i] = v[i].x;
            y[i] = v[i].y;
        }

        cout << "GATA GEN NR\n";

        return;
    }

    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)
    {
       // assert(poz <= 2*n);
      //  cout << poz << "\n";

        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);
}

//int SPEC = 0;

void comb(int a, int b, int c)
{
    int i = 0, j = 0;
/*
    if(SPEC == 1)
    {
        cout << a << " " << b << " " << c  << "\n";
        cout << g[b].size() << " " << g[c].size() << "\n";

        for(int i = 1; i < g[b].size(); i ++)
        {
            if(g[b][i] < g[b][i - 1])
                cout << "EROARE INT B\n";
        }


        for(int i = 1; i < g[c].size(); i ++)
        {
            if(g[c][i] < g[c][i - 1])
                cout << "EROARE INT C\n";
        }
    }*/

    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)
    {
        sort(g[poz].begin(), g[poz].end());
        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(st == 13412 && dr == 13413)
    {
        cout << " SUNTEM ACOLO \n";
        cout << st << " " << mid << "\n";
        cout << mid + 1 << " URM " << dr << "\n";
    }*/

    if(mid + 1 <= dr && done[poz << 1] && done[(poz << 1) + 1] && done[poz] == 0)
    {
   // if(st == 13412 && dr == 13413)
      //      SPEC = 1;
        comb(poz, poz << 1, (poz << 1) + 1), done[poz] = 1;
      //  SPEC = 0;
   // if(st == 13412 && dr == 13413)
     //   cout << " INTER\n";
    }

    else if(mid + 1 > dr && done[poz << 1] && done[poz] == 0)
    {
   // if(st == 13412 && dr == 13413)
      //  cout << "COPY\n";
        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;
//int smen[MAX_N + 1];

void getRez(int poz, int st, int dr, int a, int b, int y1, int y2)
{
    //if(poz != 0)
    //cout << " SUNTEM " << poz << " ST DR " << st << " " << dr << " X1 X2 " << a << " " << b << " Y1 Y2 " << y1 << " " << y2 << "\n";

    if(st == a && dr == b)
    {
        //cout << " EPNTRU " << st << " " << dr << " CORECT " << smen[dr] - smen[st - 1] << "\n";
        if(g[poz].size() == 0)
            return;

       // sort(g[poz].begin(), g[poz].end());
        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 --;

        //if()
/*
        cout << " ITNR E " << st << " " << dr << "\n";
        for(auto u : g[poz])
            cout << u << " " ;
        cout << "\n";
*/
  //      if(it <= it2)
    //    cout << "PENTRU " << st << " " << dr << " " << " AVEM " << y1 << " " << y2 << " " << (it2 - it + 1) << " == "

//         << smen[dr] - smen[st - 1] << "\n";

      /*   if(st == 13001 && dr == 14000)
         {
             cout << g[poz].size() << "\n";
             int cnt = 0;
             int ant = g[poz][0];
             for(auto u : g[poz])
             {
                 cnt ++;
                 if(u < ant)
                    cout << "EROARE " << u << " " << ant << " " << cnt << "\n";

                 ant = u;
             }
             cout << " AVEM CNT " << cnt << "\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);
    }
}

int getBrut(int x1, int y1, int x2, int y2)
{
    int rez = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(v[i].x >= x1 && v[i].x <= x2 && v[i].y >= y1 && v[i].y <= y2)
        {
            rez ++;
           // int c = cautBin(dx, kx, v[i].x);
           // smen[c] ++;
        }
    }

  //  for(int i = 1; i <= n; i ++)
    //    smen[i] += smen[i - 1];

    return rez;
}

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

    int q;

    if(DEBUG)
        q = MAX_Q;

    else
        f >> q;

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

        if(DEBUG == 1)
        {
            x1 = getNr();
            y1 = getNr();
            x2 = getNr();
            y2 = getNr();

            if(x1 > x2)
                swap(x1, x2);

            if(y1 > y2)
                swap(y1, y2);
        }

        else
            f >> x1 >> y1 >> x2 >> y2;

        int ax1 = x1;
        int ax2 = x2;
        int ay1 = y1;
        int ay2 = y2;

      int rez2;


      //  cout << " RUM BRUT " << q << "\n";

        //int rez2 = getBrut(x1, y1, x2, y2);

       // cout << "GATA BRUT " << rez2 << "\n";

        if(x1 > dx[kx] || x2 < dx[1] || y1 > dy[ky] || y2 < dy[1])
        {
           // if(rez2 != 0)
            //    assert(1 == 0);

            g << "0\n";

            continue;
        }

        //cout << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";

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

        if(x1 > x2 || y1 > y2)
        {
            g << "0\n";
          //  if(rez2 != 0)
            //    assert(1 == 0);


            continue;
        }

       // cout << "GATA CBIN\n";
       // cout << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
       // cout << dx[x1] << " " << dx[x2] << " " << dy[y1] << " " << dy[y2] << "\n";

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

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

       // cout << "GATA GETREZ\n";

        if(DEBUG == 1)
        {
            if(rez != rez2)
            {
              //  cout << rez << " " << rez2 << "\n";

                ofstream x("test.txt");

                x << n << "\n";
                for(int i = 1; i <= n; i ++)
                    x << v[i].x << " " << v[i].y << "\n";

                x << "1\n";
                x << ax1 << " " << ay1 << " " << ax2 << " " << ay2 << "\n";

                x.close();
            }
            assert(rez == rez2);
        }

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

int main()
{
    readFile();

    solve();

   // cout << "GATA SOLVE\n";

    ansQues();

    return 0;
}