Cod sursa(job #2618656)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 25 mai 2020 17:52:15
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 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 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});
    }
    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});
    }

    std::stable_sort (arr.begin(), arr.end(), sort_X);
    for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
        if (arr[i].x != last){
            cnt ++;
            last = arr[i].x;
        }
        arr[i].x = cnt;
    }


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

    std::stable_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;
}