Cod sursa(job #2900890)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 12 mai 2022 13:56:27
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.58 kb
#include <bits/stdc++.h>
#define NMAX 16005
#define MMAX 100005
#define POINTSMAX 218005

using namespace std;

/***********/
/// Parsare
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;
 
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
 
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
/***********/
// INPUT / OUTPUT

InParser fin("zoo.in");
ofstream g("zoo.out");
/***********/
/// GLOBAL DECLARATIONS

int N, M, P;
int arb[4 * POINTSMAX], ans[MMAX];

struct Point
{
    int x, y;
    short tip; // -1 -> animal, 0 -> stanga-sus, 1 -> stanga jos, 2 -> dreapta jos, 3 -> dreapta sus
    int idx;
} points[NMAX + 4 * MMAX];
/***********/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/***********/
///-------------------------------------
inline void ReadInput()
{
    fin >> N;

    int x, y, ind = 0;
    for (int i = 1 ; i <= N ; ++ i)
    {
        fin >> x >> y;
        points[++ind] = {x, y, -1, -1};
    }

    fin >> M;

    int x1, y1, x2, y2;
    for (int i = 1 ; i <= M ; ++ i)
    {
        fin >> x1 >> y1 >> x2 >> y2;
        points[++ind] = {x1 - 1, y2, 0, i};
        points[++ind] = {x1 - 1, y1 - 1, 1, i};
        points[++ind] = {x2, y1 - 1, 2, i};
        points[++ind] = {x2, y2, 3, i};
    }
    P = ind;
}
///-------------------------------------
bool cmpX(const Point &a, const Point &b)
{
    if (a.x == b.x)
    {
        if (a.y == b.y)
        {
            return a.tip < b.tip;
        }
        return a.y < b.y;
    }
    return a.x < b.x;
}
///-------------------------------------
inline void NormalizeX()
{
    sort(points + 1, points + P + 1, cmpX);

    int ind = 1, aux;
    for (int i = 1 ; i <= P ; ++ i)
    {
        aux = points[i].x;
        points[i].x = ind;
        if (aux < points[i + 1].x) ind ++;
    }
}
///-------------------------------------
bool cmpY(const Point &a, const Point &b)
{
    if (a.y == b.y)
    {
        if (a.x == b.x)
        {
            return a.tip < b.tip;
        }
        return a.x < b.x;
    }
    return a.y < b.y;
}
///-------------------------------------
inline void NormalizeY()
{
    sort(points + 1, points + P + 1, cmpY);

    int ind = 1, aux;
    for (int i = 1 ; i <= P ; ++ i)
    {
        aux = points[i].y;
        points[i].y = ind;
        if (aux < points[i + 1].y) ind ++;
    }
}
///-------------------------------------
void Update(int st, int dr, int arbIdx, int pos)
{
    if (st == dr)
    {
        arb[arbIdx] ++;
        return;
    }

    int mid = (st + dr) / 2;

    if (pos <= mid) Update(st, mid, 2 * arbIdx, pos);
    else Update(mid + 1, dr, 2 * arbIdx + 1, pos);
    arb[arbIdx] = arb[2 * arbIdx] + arb[2 * arbIdx + 1]; 
}
///-------------------------------------
int Query(int st, int dr, int arbIdx, int pos)
{
    if (st == dr)
    {
        return arb[arbIdx];
    }

    int mij = (st + dr) / 2;
    if (pos <= mij) return Query(st, mij, 2 * arbIdx, pos);
    return arb[2 * arbIdx] + Query(mij + 1, dr, 2 * arbIdx + 1, pos);
}
///-------------------------------------
inline void Solve()
{
    int sum, mult;
    for (int i = 1 ; i <= P ; ++ i)
    {
        if (points[i].tip == -1)
        {
            Update(0, P, 1, points[i].y);
            continue;
        }

        sum = Query(0, P, 1, points[i].y);
        if (points[i].tip & 1) mult = 1; 
        else mult = -1;

        ans[points[i].idx] += mult * sum;
    }
}
///-------------------------------------
inline void Solution()
{
    NormalizeY();
    NormalizeX();
    Solve();
}
///-------------------------------------
inline void Output()
{
    for (int i = 1 ; i <= M ; ++ i)
    {
        g << ans[i] << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}