Cod sursa(job #2505121)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 6 decembrie 2019 10:55:53
Problema Ograzi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <bits/stdc++.h>

FILE *in = fopen("ograzi.in", "r"), *out = fopen("ograzi.out", "w") ;

const int MOD = 666013 ;
const int MV = 50000 ;
const int BUF_SIZE = (1 << 17) ;
using ll = long long ;

int pos = BUF_SIZE ;
char buf[BUF_SIZE] ;

inline char nextch() {
        if (pos == BUF_SIZE) {
                fread(buf, BUF_SIZE, 1, in) ;
                pos = 0 ;
        }
        return buf[pos ++] ;
}

inline int read() {
        char ch ;
        while (!isdigit(ch = nextch())) ;
        int x = ch - '0' ;
        while (isdigit(ch = nextch())) { x = 10 * x + ch - '0' ; }
        return x ;
}



int k, ord[MV + 1], absc[MV + 1], next[MV + 1], listord[MOD] ;
ll val[MV + 1] ;
int width, height ;
bool o ;

ll hash(ll x, int y) {
        if (x < 0 || y < 0) { return 0 ; }
        else {
                return (x << 30) + y ;
        }
}

bool este(int c, int x, int y) {
        if (c == 0 && !o) { return 0 ; }
        return (x - ord[c] <= width && y - absc[c] <= height && ord[c] <= x && absc[c] <= y) ;
}

void update(ll x, int u, int v) {
        int r = x % MOD ;
        val[++ k] = x ;
        ord[k] = u ;
        absc[k] = v ;
        next[k] = listord[r] ;
        listord[r] = k ;
}

int coresphash(ll x) {
        int p = listord[x % MOD] ;
        for ( ; p != 0 && val[p] != x ; p = next[p]) ; /// hashtable de mana ca suntem smekeri
        return p ;
}

int main() {
        int n = read() ;
        int m = read() ;
        width = read() ;
        height = read() ;
        for (int i = 0 ; i < n ; i++) {
                int x = read() ;
                int y = read() ;
                update(hash(x / width, y / height), x, y) ; /// nu merge baleire :(
                                                                 /// asa ca bag O(n + m) :)
        }
        int goodSheeps = 0 ;
        for (int i = 0 ; i < m ; i++) {
                int x = read() ;
                int y = read() ;
                goodSheeps += este(coresphash(hash(x / width, y / height)), x, y) |
                              este(coresphash(hash(x / width, y / height - 1)), x, y) |
                              este(coresphash(hash(x / width - 1, y / height)), x, y) |
                              este(coresphash(hash(x / width - 1, y / height - 1)), x, y) ;
        }
        fprintf(out, "%d\n", goodSheeps) ;
}