Pagini recente » Cod sursa (job #2549823) | Cod sursa (job #2538659) | Cod sursa (job #2278789) | Cod sursa (job #31033) | Cod sursa (job #729807)
Cod sursa(job #729807)
#include<iostream>
#include<fstream>
#include<map>
using namespace std;
ifstream in("walls.in");
ofstream out("walls.out");
const int N = 100010;
int n,m,aint[3*N],h[N],w[N],xx,y,poz,x[N];
map<pair<int,int>, int> ha;
map<pair<int,int>, int>::iterator it;
void update(int nod, int pozx, int pozy) {
if(pozx == pozy) {
aint [nod] = pozx;
return;
}
int mi = (pozx + pozy)>>1;
if(poz<=mi)
update(2*nod, pozx, mi);
else
update(2*nod+1, mi+1, pozy);
aint[nod] = h[aint[2*nod]] > h[aint[2*nod+1]] ? aint[2*nod] : aint[2*nod+1];
}
int q(int nod, int pozx, int pozy) {
if(pozx > poz)
return -1;
if(pozy <= poz) {
if(pozx == pozy && h[aint[nod]]>=y)
return aint[nod];
if(h[aint[nod]]<y || pozx == pozy)
return -1;
}
int mi = (pozx + pozy)>>1;
int r = q(2*nod+1, mi+1, pozy);
if(r == -1)
r = q(2*nod, pozx, mi);
return r;
}
int main() {
int i,pas;
in >> n;
x[0] = -1;
for(i=1;i<=n;++i) {
in >> w[i] >> h[i];
x[i] = x[i-1]+w[i] + 1;
poz = i;
update(1,1,n);
}
in >> m;
while(m--) {
in >> xx >> y;
pas = 1<<18;
for(i = 0; pas!=0; pas>>=1)
if(i+pas<=n && x[i+pas]<xx)
i+=pas;
poz = i;
int res = q(1,1,n),ver = 0;
if(res == -1) {
out << "MISS\n";
continue;
}
out << "HIT ";
++ha[make_pair(res, y)];
it = ha.find(make_pair(res,y));
out << x[res] - it->second+1 << " ";
if(it->second == w[res]) {
ver = 1;
h[res] = y - 1;
poz = res;
update(1,1,n);
}
out << res << " ";
if(ver)
out << "YES\n";
else
out << "NO\n";
}
return 0;
}