Cod sursa(job #2618662)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 25 mai 2020 18:06:48
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb

#include <bits/stdc++.h>
#define maxn 250005
std::ofstream fout ("zoo.out");

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

struct str{
    int x, y, type, index;
};

std::vector <str> arr;
bool sort_cond (str a, str b){
    if (a.y != b.y) return a.y < b.y;
    return a.type > b.type;
}
bool sort_X (str a, str b){
    return a.x < b.x;
}

bool sort_Y (str a, str b){
    return a.y < b.y;
}


int bit[maxn];
void update (int pos, int val){
    while (pos < maxn){
        bit[pos] += val;
        pos = (pos | (pos+1));
    }
}
int query (int pos){
    int ans = 0;
    while (pos >= 0){
        ans += bit[pos];
        pos = (pos & (pos+1)) - 1;
    }
    return ans;
}

int ans[maxn];
int x[maxn], size;
std::map < int, int > mp;
int main()
{
    InParser fin ("zoo.in");
    int n, i, Q;
    int x1, y1, x2, y2;
    int cnt, last;
    fin >> n;
    for (i=0; i<n; i++){
        fin >> x1 >> y1;
        arr.push_back ({x1, y1, 2, i});
        x[size++] = x1;
    }
    fin >> Q;
    for (i=0; i<Q; i++){
        fin >> x1 >> y1 >> x2 >> y2;
        arr.push_back ({x2, y2, 1, i});
        arr.push_back ({x1-1, y1-1, 1, i});
        arr.push_back ({x2, y1-1, -1, i});
        arr.push_back ({x1-1, y2, -1, i});
        x[size++] = x1-1;
        x[size++] = y2;
    }
    std::sort (x, x+size);
    for (i=0, cnt=0; i<size; i++){
        if (mp[x[i]] == 0)
            mp[x[i]] = cnt++;
    }
    for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
        arr[i].x = mp[arr[i].x];
    }


    //for (i=0; i<arr.size(); i++)
    //    fout << arr[i].x << ' ' << arr[i].y << ' ' << arr[i].type << ' ' << arr[i].index << '\n';

    std::sort (arr.begin(), arr.end(), sort_cond);

    for (i=0;i < arr.size(); i++){
        if (arr[i].type == 2)
            update (arr[i].x, 1);
        else
            ans[arr[i].index] += arr[i].type * query (arr[i].x);
    }

    for (i=0; i<Q; i++)
        fout << ans[i] << '\n';


    return 0;
}