Cod sursa(job #984327)

Utilizator stefanzzzStefan Popa stefanzzz Data 14 august 2013 09:46:46
Problema Ograzi Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <algorithm>
#define MAXCORD 1000005
#define MAXS 25
#define MAXN 50005
#define MAXM 100005
using namespace std;
ifstream f("ograzi.in");
ofstream g("ograzi.out");

struct event{
    bool tip;
    int x,y;};

int n,m,w,h,cnt,sol,cord,nrev,xx,yy;
bool ai[4*MAXCORD];
char s[25];
event ev[MAXN+MAXM];

bool Comp(event a,event b){
    if(a.x==b.x)
        return a.tip<b.tip;
    return a.x<b.x;}

int getnr();
void query(int nod,int st,int dr);
void update(int nod,int st,int dr);

int main()
{
    int i;
    f>>n>>m>>w>>h;
    f.getline(s,MAXS,'\n');
    for(i=1;i<=n;i++){
        f.getline(s,MAXS,'\n');
        cnt=0;
        ev[++nrev].x=ev[nrev+1].x=getnr();
        ev[nrev].y=ev[nrev+1].y=getnr();
        ev[++nrev].x+=w+1;}
    for(i=1;i<=m;i++){
        f.getline(s,MAXS,'\n');
        cnt=0;
        ev[++nrev].x=getnr();
        ev[nrev].y=getnr();
        ev[nrev].tip=1;}
    n=nrev;
    sort(ev+1,ev+n+1,Comp);
    cord=MAXCORD-2;
    for(i=1;i<=n;i++){
        xx=ev[i].y;
        if(ev[i].tip)
            query(1,1,cord);
        else{
            yy=xx+h;
            update(1,1,cord);}}
    g<<sol<<'\n';
    f.close();
    g.close();
    return 0;
}

int getnr(){
    int a=0;
    while(s[cnt]>='0'&&s[cnt]<='9')
        a=a*10+s[cnt++]-'0';
    cnt++;
    return a+1;}

void query(int nod,int st,int dr){
    if(ai[nod]){
        sol++;
        return;}
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(xx<=mij)
        return query(2*nod,st,mij);
    else
        return query(2*nod+1,mij+1,dr);}

void update(int nod,int st,int dr){
    if(st>=xx&&dr<=yy){
        ai[nod]=1-ai[nod];
        return;}
    int mij=(st+dr)/2;
    if(xx<=mij)
        update(2*nod,st,mij);
    if(yy>mij)
        update(2*nod+1,mij+1,dr);}