Cod sursa(job #220429)

Utilizator savimSerban Andrei Stan savim Data 10 noiembrie 2008 20:49:04
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100000
#define MAX_L 417000
#define inf 2147000000

int n, m, i, j, k, x1, y1, x2, y2, p, q, sum, i1, i2, semn;
int aib[MAX_L];
int intreb[MAX_L];
int ordon[MAX_L], v[MAX_L];
int qry[2][MAX_N];
char s[60];

struct punct {
	int x;
	int y;
};

punct a[MAX_L], b[MAX_L];

void cit() {
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	 //citirea parsata  
    scanf("%d\n",&n);  
    for (i = 1; i <= n; v[i] = i, i++)   
        scanf("%d %d",&a[i].x, &a[i].y);  
      
    scanf("%d\n", &m);  
    for (i = 1; i <= m; i++) {  
        fgets(s,50,stdin);  
          
        j = 0;  
        semn = 1;x1 = 0;  
        if (s[j] == '-') {semn = -1; j++;}  
        for (j = j; s[j] != ' '; j++)  
            x1 = x1 * 10 + s[j] - '0';  
        x1 *= semn;  
          
        j++;  
        semn = 1; y1 = 0;  
        if (s[j] == '-') {semn = -1; j++;}  
        for (j = j; s[j] != ' '; j++)  
            y1 = y1 * 10 + s[j] - '0';  
        y1 *= semn;  
          
        j++;  
        semn = 1; x2 = 0;  
        if (s[j] == '-') {semn = -1; j++;}  
        for (j = j; s[j] != ' '; j++)  
            x2 = x2 * 10 + s[j] - '0';  
        x2 *= semn;  
          
        j++;  
        semn = 1; y2 = 0;  
        if (s[j] == '-') {semn = -1; j++;}  
        for (j = j; s[j] != '\n' && s[j] != '\0'; j++)  
            y2 = y2 * 10 + s[j] - '0';  
        y2 *= semn;  
  
        a[++n].x = x1 - 1; a[n].y = y1 - 1; intreb[n] = i;  
        a[++n].x = x1 - 1; a[n].y = y2; intreb[n] = i;  
        a[++n].x = x2; a[n].y = y1 - 1; intreb[n] = i;  
        a[++n].x = x2; a[n].y = y2; intreb[n] = i;  
    }         
}
inline int cmp2(int a, int b) {
	return ordon[a] < ordon[b];
}

void normalizare () {
	p = 1; q = 1;
	for (i = 1; i <= n; i++) {
		b[i].x = p;
		if (a[i].x > a[i - 1].x) b[i].x = ++p;

		ordon[i]  = a[i].y;
		v[i] = i;
	}

	sort(v + 1, v + n + 1, cmp2);

	for (i = 1; i <= n; i++) {
		b[v[i]].y = q;
		if (ordon[v[i]] > ordon[v[i - 1]]) b[v[i]].y = ++q;
	}
}

void update(int k) {
	while (k <= q) {
	    aib[k]++;
		k += k ^ (k & (k - 1));
	}
}

int query(int k) {
	sum = 0;
	while (k) {
		sum += aib[k];
		k -= k ^ (k & (k - 1));
	}
	return sum;
}

void parcurg() {
	for (i = 1; i <= n; i++) {
		//update
		if (intreb[i] == 0) update(b[i].y);
		
		//query
		if (intreb[i] != 0) {
           p = intreb[i];
		   qry[0][p]++;
		   if (qry[0][p] == 1) qry[1][p] += query(b[i].y);
		   if (qry[0][p] == 2) qry[1][p] -= query(b[i].y);
		   if (qry[0][p] == 3) qry[1][p] -= query(b[i].y);
		   if (qry[0][p] == 4) qry[1][p] += query(b[i].y);
        }   
	}
}

void inter(int p, int q) {
     int r = (p + q) >> 1; k = 0, i1 = p, i2 = r + 1;
     
     while (i1 <= r && i2 <= q) {
           if ((a[i1].x < a[i2].x) || (a[i1].x == a[i2].x && a[i1].y < a[i2].y)||
               (a[i1].x == a[i2].x && a[i1].y == a[i2].y && intreb[i1] < intreb[i2])) {
               b[++k].x = a[i1].x; b[k].y = a[i1].y; ordon[k] = intreb[i1]; i1++;
           }
           else { b[++k].x = a[i2].x; b[k].y = a[i2].y; ordon[k] = intreb[i2]; i2++;}
     }
     
     while (i1 <= r) {b[++k].x = a[i1].x; b[k].y = a[i1].y; ordon[k] = intreb[i1]; i1++;};
     while (i2 <= q) {b[++k].x = a[i2].x; b[k].y = a[i2].y; ordon[k] = intreb[i2]; i2++;};
     
     k = 0;
     for (i = p; i <= q; i++) {
         a[i].x = b[++k].x; a[i].y = b[k].y; intreb[i] = ordon[k];
     }
}

void merge(int p, int q) {
     if (p >= q) return;
     int r = (p + q) >> 1;
     merge(p, r);
     merge(r + 1, q);
     inter(p, q);
}

void solve() {
	//sortarea elementelor
	merge(1, n);
	
	//normalizarea elementelor
	normalizare();
	
	//parcurgerea elementelor si query - urile respective
	parcurg();  
}

void write() {
	for (i = 1; i <= m; i++)
		printf("%d\n", qry[1][i]);
}

int main() {

	cit();
	solve();
	write(); 
	
	return 0;
}