Cod sursa(job #3291761)

Utilizator ana.veronica13Ana Veronica Draghici ana.veronica13 Data 5 aprilie 2025 14:56:33
Problema Ograzi Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

#define MAX_N 50001
#define MAX_M 100001

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 oaie{
  int x, y, xparcela, yparcela;
};

oaie o[MAX_M];
int x[MAX_N], y[MAX_N], ldir[4] = { 0, 1, 1, 0}, cdir[4] = { 0, 0, 1, 1 };

int cmp( oaie a, oaie b ){
  if( a.xparcela != b.xparcela )
    return a.xparcela < b.xparcela;
  return a.yparcela < b.yparcela;
}

int main(){
  InParser cin( "ograzi.in" );
  ofstream cout( "ograzi.out" );
  int n, m, w, h, ans, i, j, k, lin, col, d, st, dr, mid;
  cin >> n >> m >> w >> h;
  for( i = 0; i < n; i++ ){
    cin >> x[i] >> y[i];
  }
  h++;
  w++;
  for( i = 0; i < m; i++ ){
    cin >> o[i].x >> o[i].y;
    o[i].xparcela = o[i].x / w;
    o[i].yparcela = o[i].y / h;
  }
  sort( o, o + m, cmp );
  ans = 0;
  for( i = 0; i < n; i++ ){
    for( d = 0; d < 4; d++ ){
      lin = x[i] + w * ldir[d];
      col = y[i] + h * cdir[d];
      lin /= w;
      col /= h;
      st = -1;
      dr = m;
      //printf("a");
      while( dr - st > 1 ){
    //    printf( "%d %d\n", st, dr);
        mid = ( dr + st ) / 2;
        if( o[mid].xparcela < lin || ( o[mid].xparcela == lin && o[mid].yparcela < col ) )
          st = mid;
        else
          dr = mid;
      }
      j = dr;
      st = -1;
      dr = m;
      while( dr - st > 1 ){
        mid = ( st + dr ) / 2;
        if( o[mid].xparcela < lin || ( o[mid].xparcela == lin &&  o[mid].yparcela <= col ) )
          st = mid;
        else
          dr = mid;
      }
     // cout << j << " " << st << "\n";
      for( ; j <= st; j++ ){
        if( o[j].x >= x[i] && o[j].x < x[i] + w && o[j].y >= y[i] && o[j].y < y[i] + h ){
          ans++;
        //  cout << j << " " << i << "\n";
        }
      }
    }
  }
  cout << ans;
    return 0;
}