Cod sursa(job #543524)

Utilizator feelshiftFeelshift feelshift Data 28 februarie 2011 10:49:50
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
// 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;
}