Pagini recente » Cod sursa (job #2455787) | Cod sursa (job #2854820) | Cod sursa (job #2839212) | Cod sursa (job #684285) | Cod sursa (job #544233)
Cod sursa(job #544233)
#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);
map< pair<int,int>, int> h;
int N,M;
long long w[MaxN],tx[MaxN],px;
int ty[MaxN],py;
int aint[aint_SIZE];
int update_pos,update_val;
int query_st,query_dr,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(aint[nod]<py || st>query_dr)
{
return;
}
if(st==dr)
{
query_pos=st;
return;
}
int l=nod<<1;
int m=st+((dr-st)>>1);
if(aint[l|1]>=py)
{
query(m+1,dr,l|1);
}
if(query_pos==-1)
{
query(st,m,l);
}
}
int cautbin(long long x)
{
int first=1;
int step=1;
for(;step<=N;step<<=1);
for(;step;step>>=1)
{
int index=first+step;
if(index<=N && tx[index]<x)
{
first=index;
}
}
if(tx[first]<x)
{
return first;
}
return -1;
}
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>w[i]>>ty[i];
tx[i]=w[i]+tx[i-1]+1;
update_val=ty[i];
update_pos=i;
update(1,N,1);
}
fin>>M;
for(register int i=1;i<=M;++i)
{
fin>>px>>py;
query_pos=-1;
query_st=1;
query_dr=cautbin(px+1);
query(1,N,1);
if(query_pos==-1)
{
fout<<"MISS\n";
}
else
{
int poz=query_pos;
int &hit=h[make_pair(poz,py)];
if(++hit==w[poz])
{
update_pos=poz;
update_val=py-1;
update(1,N,1);
fout<<"HIT "<<tx[poz]-hit<<" "<<poz<<" YES\n";
}
else
{
fout<<"HIT "<<tx[poz]-hit<<" "<<poz<<" NO\n";
}
}
}
fin.close();
fout.close();
return 0;
}