Cod sursa(job #963714)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 18 iunie 2013 16:12:33
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("ograzi.in");
ofstream g("ograzi.out");

#define mp make_pair
#define x first
#include <set>
#define y second
#define LE 100666

multiset <int>  SET;
multiset<int> :: iterator it ;

int nrgr,nroi,lat,h;
pair<int,int> X[LE],oi[LE];
int i,result;


int main()
{
    f>>nrgr>>nroi>>lat>>h;

    for(i=1;i<=nrgr;++i)
      f>>X[i].x>>X[i].y;
    sort(X+1,X+nrgr+1);

    for(i=1;i<=nroi;++i)
      f>>oi[i].x>>oi[i].y;
    sort(oi+1,oi+nroi+1);


    int top_push=0;
    int top_erase=0;

    for(i=1;i<=nrgr;++i) cout<<X[i].x<<" "<<X[i].y<<" "<<'\n';

    for(i=1;i<=nroi;++i){

      while (top_push<nrgr&&X[top_push+1].x+lat>=oi[i].x&&X[top_push+1].x<=oi[i].x){
        ++top_push;
        SET.insert(X[top_push].y);
      }

      while (top_erase<nrgr&&X[top_erase+1].x+lat<oi[i].x){
        SET.erase(SET.find(X[top_erase+1].y));
        ++top_erase;
      }

if (SET.empty()==true) continue;
      it=SET.upper_bound(oi[i].y);


      if (it==SET.begin())
        continue;
      else{

       --it;
       if ((*it)+h>=oi[i].y) {++result;
      cout<<*it<<'\n';
       }
      }
    }

   g<<result<<'\n';
    f.close();
    g.close();
    return 0;
}