Cod sursa(job #2634936)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 12 iulie 2020 19:00:59
Problema Ograzi Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 5e4 + 5, MMAX = 1e5 + 5;
const int BEGIN = -1, QUERY = 0, END = 1;
const int INF = 1e9;

int N, M, W, H, Max = -INF;

int MAX = -INF;

struct Event
{
    short int Type;

    int X, Y1, Y2;
};

int q = 0;
Event V[(NMAX << 1) + MMAX];

namespace InParser
{
static const int BSIZE = (1 << 16);

static int pos = BSIZE - 1;
static char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

inline int Int ()
{
    int ans = 0, sign = 1;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch == '-')
        {
            sign = -1;

            break;
        }

        if(Ch >= '0' && Ch <= '9')
        {
            ans = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            ans = ans * 10 + (int)(Ch - '0');
        else
            break;
    }

    return (ans * sign);
}
};

class FenwickTree
{
    static const int VMAX = 1e6 + 5;
    int a[VMAX];

private:
    static inline int UB (int X)
    {
        return (X & (-X));
    }

    inline void Update (int pos, int Val)
    {
        for(int i = pos; i <= Max; i += UB(i))
            a[i] += Val;

        return;
    }

public:
    inline void Go (int Left, int Right, int Val)
    {
        Update(Left, Val);
        Update(Right + 1, -Val);

        return;
    }

    inline int Query (int pos)
    {
        int ans = 0;

        for(int i = pos; i >= 1; i -= UB(i))
            ans += a[i];

        return ans;
    }
} AIB;

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("ograzi.in", "r", stdin);
    freopen("ograzi.out", "w", stdout);

    N = InParser :: Int(), M = InParser :: Int();
    W = InParser :: Int(), H = InParser :: Int();

    for(int i = 1; i <= N; ++i)
    {
        int X1 = InParser :: Int(), Y1 = InParser :: Int();
        int X2 = X1 + W, Y2 = Y1 + H;

        Max = max(Max, (Y2 + 1));
        MAX = max(MAX, X2);

        V[++q] = {BEGIN, X1, Y1, Y2};
        V[++q] = {END, X2, Y1, Y2};
    }

    for(int i = 1; i <= M; ++i)
    {
        int X = InParser :: Int(), Y1 = InParser :: Int();

        Max = max(Max, (Y1 + 1));
        MAX = max(MAX, X);

        V[++q] = {QUERY, X, Y1, Y1};
    }

    return;
}

auto cmp = [] (Event A, Event B)
{
    if(A.X < B.X)
        return 1;

    if(A.X > B.X)
        return 0;

    if(A.Type < B.Type)
        return 1;

    return 0;
};

static inline void Solve ()
{
    sort(V + 1, V + q + 1, cmp);

    int ans = 0;

    for(int i = 1; i <= q; ++i)
        if(V[i].Type == BEGIN)
            AIB.Go(V[i].Y1, V[i].Y2, 1);
        else if(V[i].Type == END)
        {
            if(V[i].X == MAX)
                break;

            AIB.Go(V[i].Y1, V[i].Y2, -1);
        }
        else
        {
            if(AIB.Query(V[i].Y1) > 0)
                ++ans;
        }

    printf("%d\n", ans);

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}