Pagini recente » Cod sursa (job #186838) | Cod sursa (job #2600300) | Cod sursa (job #1509634) | Cod sursa (job #1314130) | Cod sursa (job #544255)
Cod sursa(job #544255)
#include <fstream>
#include <map>
using namespace std;
const char InFile[]="walls.in";
const char OutFile[]="walls.out";
const int MaxN=100111;
const int aint_SIZE=1<<18;
ifstream fin(InFile);
ofstream fout(OutFile);
struct vector2d{int x,y;};
map< pair<int,int>, int> h;
vector2d v[MaxN];
int N,M;
int aint[aint_SIZE];
long long poz[MaxN],px,py;
int update_val,update_pos;
int query_pos;
void update(int st,int dr,int nod)
{
if(st==dr)
{
aint[nod]=update_val;
return;
}
int l=nod<<1;
int m=st+((dr-st)>>1);
if(update_pos<=m)
{
update(st,m,l);
}
else
{
update(m+1,dr,l|1);
}
aint[nod]=max(aint[l],aint[l|1]);
}
void query(int st,int dr,int nod)
{
if(px<poz[st] || aint[nod]<py)
{
return;
}
if(st==dr)
{
query_pos=st;
return;
}
int l=nod<<1;
int m=st+((dr-st)>>1);
query(m+1,dr,l|1);
if(!query_pos)
{
query(st,m,l);
}
}
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>v[i].x>>v[i].y;
poz[i]=1+poz[i-1]+v[i-1].x;
update_pos=i;
update_val=v[i].y;
update(1,N,1);
}
fin>>M;
for(register int i=1;i<=M;++i)
{
fin>>px>>py;
query_pos=0;
query(1,N,1);
if(query_pos)
{
fout<<"HIT ";
pair<int,int> cell=make_pair(query_pos,py);
++h[cell];
fout<<poz[query_pos]+v[query_pos].x-h[cell]<<" "<<query_pos;
if(h[cell]==v[query_pos].x)
{
update_pos=query_pos;
update_val=py-1;
update(1,N,1);
fout<<" YES\n";
}
else
{
fout<<" NO\n";
}
}
else
{
fout<<"MISS\n";
}
}
fin.close();
fout.close();
return 0;
}