Pagini recente » Cod sursa (job #3175095) | Cod sursa (job #1718642) | Cod sursa (job #167433) | Cod sursa (job #2890718) | Cod sursa (job #595895)
Cod sursa(job #595895)
#include <iostream>
#include <fstream>
#include <map>
#define DN 1000005
#define DA 4*DN
#define LL long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> per;
per v[DN];
int ai[DA],n,m,p,val,gls,gld;
LL poz[DN];
map<per,int> mp;
void update(int vn, int ls, int ld) {
if(ls==ld) {
ai[vn]=val;
return;
}
int m=(ls+ld)>>1,fs=vn<<1;
if(p<=m) update(fs,ls,m);
else update(fs+1,m+1,ld);
ai[vn]=max(ai[fs],ai[fs+1]);
}
int query(int vn, int ls, int ld) {
if(gls<poz[ls] || gld>ai[vn]) return 0;
if(ls==ld) return ls;
int ret,m=(ls+ld)>>1,fs=vn<<1;
ret=query(fs+1,m+1,ld);
if(0==ret) ret=query(fs,ls,m);
return ret;
}
int main()
{
ifstream f("walls.in");
ofstream g("walls.out");
f>>n;
for(int i=1; i<=n; ++i) {
f>>v[i].x>>v[i].y;
p=i; val=v[i].y;
update(1,1,n);
poz[i]=poz[i-1]+v[i-1].x+1;
}
f>>m;
for(int i=1; i<=m; ++i) {
f>>gls>>gld;
int sol=query(1,1,n);
if(0==sol) g<<"MISS\n";
else {
g<<"HIT ";
if(mp.find(make_pair(sol,gld))!=mp.end()) ++mp[make_pair(sol,gld)];
else mp[make_pair(sol,gld)]=1;
gls=poz[sol]+v[sol].x-mp[make_pair(sol,gld)];
g<<gls<<' '<<sol<<' ';
if(gls==poz[sol]) {
g<<"YES\n";
p=sol; val=gld-1;
update(1,1,n);
}else g<<"NO\n";
}
}
return 0;
}