Cod sursa(job #2704655)

Utilizator euyoTukanul euyo Data 10 februarie 2021 21:55:45
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin( "zoo.in" );
ofstream fout( "zoo.out" );  

using namespace std;

const int Max = 250000;

struct event {
  int x, y, type, ind, nq;
} q[Max];

int tree[4 * Max];

inline int left( int node ) { 
  return node << 1;
}
inline int right( int node ) {
  return (node << 1) | 1;
}

int ux;
void update( int node, int l, int r ) {
  if ( l == r ) {
	++tree[node];
	return;
  }
  int mid = (l + r) / 2;
  if ( ux <= mid ) {
	update( left( node ), l, mid );
  } else {
	update( right( node ), mid + 1, r );
  }
  tree[node] = tree[left( node )] + tree[right( node )];
}

int qa, qb;
int query( int node, int l, int r ) {
  int x = 0, y = 0;
  
  if ( qa <= l && r <= qb ) {
	return tree[node];
  }
  int mid = (l + r) / 2;
  if ( qa <= mid ) {
    x = query( left( node ), l, mid );
  }
  if ( qb > mid ) {
	y = query( right( node ), mid + 1, r );
  }
  return x + y;
}

struct cmpx {
  bool operator () ( const event &a, const event &b ) {
	return (a.x < b.x) || (a.x == b.x && a.type < b.type);
  }
};
struct cmpy {
  bool operator () ( const event &a, const event &b ) {
    return a.y < b.y;
  }
};

event nx[Max], ny[Max];
int res[Max];
int _y1[Max], _y2[Max];

int main() {
  int n, m, nev;

  fin >> n;
  nev = 0;
  for ( int i = 0; i < n; ++i ) {
    fin >> q[nev].x >> q[nev].y;
	q[nev].type = 0;
	q[nev].ind = nev;
	nx[nev] = ny[nev] = q[nev];
	++nev;
  }
  fin >> m;
  for ( int i = 0; i < m; ++i ) {
	fin >> q[nev].x >> q[nev].y;
	q[nev].type = -1;
	q[nev].ind = nev;
	++nev;
	fin >> q[nev].x >> q[nev].y;
	q[nev].type = 1;
	q[nev].ind = nev;
	q[nev - 1].nq = q[nev].nq = i;
	nx[nev - 1] = ny[nev - 1] = q[nev - 1];
	nx[nev] = ny[nev] = q[nev];
	++nev;
  }
  sort( ny, ny + nev, cmpy() );
  int cry = 1;
  q[ny[0].ind].y = cry;
  for ( int i = 1; i < nev; ++i ) {
	if ( ny[i - 1].y == ny[i].y ) {
	  q[ny[i].ind].y = cry;
	} else {
	  q[ny[i].ind].y = ++cry;
	}
  }
  sort( q, q + nev, cmpx() );
  for ( int i = 0; i < nev; ++i ) {
	if ( q[i].type == -1 ) {
	  _y1[q[i].nq] = q[i].y;
	}
	if ( q[i].type == 1 ) {
	  _y2[q[i].nq] = q[i].y;
	}
  }
  for ( int i = 0; i < nev; ++i ) {
	if ( q[i].type == 0 ) {
	  ux = q[i].y;
      update( 1, 1, cry );  
	} else if ( q[i].type == -1 ) {
      qa = _y1[q[i].nq], qb = _y2[q[i].nq];
	  res[q[i].nq] = query( 1, 1, cry );
	} else if ( q[i].type == 1 ) {
	  qa = _y1[q[i].nq], qb = _y2[q[i].nq];
	  res[q[i].nq] = query( 1, 1, cry ) - res[q[i].nq];
	}
  }
  for ( int i = 0; i < m; ++i ) {
	fout << res[i] << "\n";
  } 
  fin.close();
  fout.close();
  return 0;
}