Cod sursa(job #994812)

Utilizator primulDarie Sergiu primul Data 6 septembrie 2013 13:34:15
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<cstdio>
#include<map>
using namespace std;
 
int N,M,wall,pas,px,py,i,j,poz,x[100001],w[100001],h[100001],tree[500005];
map<pair<int,int>, int> MAP;
map<pair<int,int>, int>::iterator it;
 
 
void update(int nod, int left, int right)
{if(left==right)
  {tree[nod]=left;
  return;}
 int mid=(left+right)/2;
 if(poz<=mid)
   update(2*nod,left,mid);
 else
   update(2*nod+1,mid+1,right);
  
 if(h[tree[2*nod]]<=h[tree[2*nod+1]])  
    tree[nod]=tree[2*nod+1];
 else
    tree[nod]=tree[2*nod];   
}
 
int query(int nod, int left, int right)
{if(left>px)
   return -1;
 if(right<=px)  
   {if(left==right && h[tree[nod]]>=py)
          return tree[nod];
    if(h[tree[nod]]<py) 
          return -1;}
 int mid=(left+right)/2;
 int r=query(2*nod+1,mid+1,right);
 if(r==-1)
    r=query(2*nod,left,mid);       
 return r;   
}
 
int main()
{freopen("walls.in","r",stdin);
freopen("walls.out","w",stdout);
scanf("%d ",&N);
x[0]=-1;
for(i=1; i<=N; i++)
{scanf("%d %d",&w[i],&h[i]);
 x[i]=x[i-1]+1+w[i];
 poz=i;
 update(1,1,N);}
  
scanf("%d ",&M); 
for(i=1; i<=M; i++)
{scanf("%d %d",&px,&py);
  
 j=0;
 pas=1<<17;
 while(pas>0)
 {if(j+pas<=N && x[j+pas]<px)
    j+=pas;
 pas=pas/2;
 }
 
 px=j;
 wall=query(1,1,N);
 if(wall==-1)
   {printf("MISS\n");
   continue;}
 else
   printf("HIT ");  
    
 MAP[make_pair(wall,py)]++;  
 it=MAP.find(make_pair(wall,py));
 printf("%d %d ",(x[wall]-(it->second)+1),wall);
  
 if(it->second == w[wall])
   {h[wall]=py-1;
    printf("YES\n");
    poz=wall;
    update(1,1,N);
    }
 else
    printf("NO\n");
  
 }
 
return 0;}