Cod sursa(job #2408348)

Utilizator xRoALexBirtoiu Alexandru xRoALex Data 17 aprilie 2019 20:47:18
Problema Ograzi Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#define Nmax 100005
#define Val_max 1000005

using namespace std;


struct element
{
    int x,y,id;
};

int n,m,w,h,ans;
int aib[Val_max+2];
vector <element> drept;
vector <pair<int,int>> oi;

FILE *f = freopen("ograzi.in", "r", stdin);
FILE *g = freopen("ograzi.out", "w", stdout);

inline bool cmp(element a,element b)
{
    if(a.y==b.y)
        return a.id<b.id;
    return a.y<b.y;
}

inline bool cmp2(pair<int,int> a, pair<int,int> b)
{
    return a.second<b.second;
}

void adauga(int x)
{
    while(x<=Nmax)
    {
        aib[x]++;
        x += (x&(-x));
    }
}

int query(int x)
{
    int s=0;
    while(x)
    {
        s += aib[x];
        x-=(x&(-x));
    }
    return s;
}

char buff[4096];
int p;

/*istream& operator >> (istream& in, int& x){
    while(p < s.size() && s[p] == ' ')
        p++;
    while(p >= s.size()){
        in >> s;
        p = 0;
    }

    x = 0;
    while(p < s.size() && s[p] >= '0' && s[p] <= '9'){
        x = x * 10 + s[p] - '0';
        p++;
    }

    return in;
}
*/


const int kBufferSize = 1e5;

class InputReader {
public:
    char buffer[kBufferSize];
    int cursor;

    void getBuffer() {
      cursor = 0; fread(buffer, 1, kBufferSize, stdin);
    }

    InputReader() {
      getBuffer();
    }

    bool digit(char c) {
      return '0' <= c && c <= '9';
    }

    InputReader& operator >>(int &number) {
      char sgn = '+';
      while(!digit(buffer[cursor])) {
        sgn = buffer[cursor];
        if(++cursor == kBufferSize) {
          getBuffer();
        }
      }

      number = 0;
      while(digit(buffer[cursor])) {
        number = number * 10 + buffer[cursor] - '0';
        if(++cursor == kBufferSize) {
          getBuffer();
        }
      }

      number = (sgn == '-') ? -number : number;

      return *this;
    }
} cin;


int main()
{
    cin>>n;
    cin>>m;
    cin>>w;
    cin>>h;
    for(int i=1;i<=n;i++)
    {
        int x,y;

        cin>>x;
        cin>>y;
        x++;
        drept.push_back({x,y,0});
        drept.push_back({x,y+h,1});
    }
    sort(drept.begin(),drept.end(),cmp);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x;
        cin>>y;
        x++;
        oi.push_back({x,y});
    }
    sort(oi.begin(),oi.end(),cmp2);
    /*for(int i=0;i<drept.size();i++)
    {
        fprintf(g,"%d %d %d\n",drept[i].x,drept[i].y,drept[i].id);

    }
    fprintf(g,"\n\n");
    for(int i=0;i<oi.size();i++)
    {
        fprintf(g,"%d %d\n",oi[i].first,oi[i].second);

    }
    fprintf(g,"\n");*/
    int k=0;
    for(int i=0;i<drept.size();i++)
    {
        if(drept[i].id==1)
        {
            while(oi[k].second<=drept[i].y)
        {
            adauga(oi[k].first);
            k++;
        }
        }
        else
        while(oi[k].second<drept[i].y)
        {
            adauga(oi[k].first);
            k++;
        }

        if(drept[i].id ==0)
            ans -= query(drept[i].x+w) - query(drept[i].x);
        else
            ans += query(drept[i].x+w) - query(drept[i].x);
    }
    fprintf(g,"%d",ans);
    return 0;
}