Pagini recente » Cod sursa (job #1910669) | Cod sursa (job #716731) | Cod sursa (job #812921) | Cod sursa (job #994689) | Cod sursa (job #543524)
Cod sursa(job #543524)
// http://infoarena.ro/problema/walls
#include <fstream>
#include <vector>
#include <map>
using namespace std;
#define maxSize 100001
#define leftSon 2*node
#define rightSon 2*node+1
ifstream in("walls.in");
ofstream out("walls.out");
int walls,bombs;
int x,y;
int position;
int currentWidth,currentHeight;
pair<int,int> wall[maxSize];
long long location[maxSize];
int tree[4*maxSize];
map< pair<int,int>, int> height;
void update(int node,int left,int right);
int query(int node,int left,int right);
int main() {
in >> walls;
for(position=1;position<=walls;position++) {
in >> wall[position].first >> wall[position].second;
currentHeight = wall[position].second;
update(1,1,walls);
location[position] = location[position-1] + 1 + wall[position-1].first;
}
in >> bombs;
int solution;
for(int i=1;i<=bombs;i++) {
in >> x >> y;
solution = query(1,1,walls);
if(!solution)
out << "MISS\n";
else {
out << "HIT ";
if(height.find(make_pair(solution,y)) != height.end())
height[make_pair(solution,y)]++;
else
height[make_pair(solution,y)] = 1;
x = location[solution] + wall[solution].first - height[make_pair(solution,y)];
out << x << " " << solution << " ";
if(x == location[solution]) {
out << "YES\n";
position = solution;
currentHeight = y - 1;
update(1,1,walls);
}
else
out << "NO\n";
}
}
in.close();
out.close();
return (0);
}
void update(int node,int left,int right) {
if(left == right)
tree[node] = currentHeight;
else {
int middle = (left + right) / 2;
if(position <= middle)
update(leftSon,left,middle);
else
update(rightSon,middle+1,right);
tree[node] = max(tree[leftSon],tree[rightSon]);
}
}
int query(int node,int left,int right) {
if(x < location[left] || y > tree[node])
return (0);
if(left == right)
return left;
int answer;
int middle = (left + right) / 2;
answer = query(rightSon,middle+1,right);
if(!answer)
answer = query(leftSon,left,middle);
return answer;
}