Cod sursa(job #543549)

Utilizator feelshiftFeelshift feelshift Data 28 februarie 2011 11:31:17
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
// http://infoarena.ro/problema/walls
#include <fstream>
#include <map>
using namespace std;

#define maxSize 100001
#define x first
#define y second
#define leftSon 2*node
#define rightSon 2*node+1

ifstream in("walls.in");
ofstream out("walls.out");

struct stuff {
    long long x;
    int width;
    int height;
};

int nrWalls,bombs;
stuff wall[maxSize];
int tree[4*maxSize];
map< pair<int,int>, int> height;

void update(int node,int left,int right,int position,int value);
int query(int node,int left,int right,int x,int height);

int main() {
    in >> nrWalls;

    for(int i=1;i<=nrWalls;i++) {
        in >> wall[i].width >> wall[i].height;
        wall[i].x = wall[i-1].x + wall[i-1].width + 1;

        update(1,1,nrWalls,i,wall[i].height);
    }

    in >> bombs;

    int solution;
    int x;
    pair<int,int> currentBomb;
    for(int i=1;i<=bombs;i++) {
        in >> currentBomb.x >> currentBomb.y;

        solution = query(1,1,nrWalls,currentBomb.x,currentBomb.y);

        if(!solution)
            out << "MISS\n";
        else {
            out << "HIT ";

            if(height.find(make_pair(solution,currentBomb.y)) != height.end())
                height[make_pair(solution,currentBomb.y)]++;
            else
                height[make_pair(solution,currentBomb.y)] = 1;

            x = wall[solution].x + wall[solution].width - height[make_pair(solution,currentBomb.y)];

            out << x << " " << solution << " ";

            if(x == wall[solution].x) {
                out << "YES\n";
                update(1,1,nrWalls,solution,currentBomb.y-1);
            }
            else
                out << "NO\n";
        }
    }

    in.close();
    out.close();

    return (0);
}

void update(int node,int left,int right,int position,int value) {
    if(left == right)
        tree[node] = value;
    else {
        int middle = (left + right) >> 1;

        if(position <= middle)
            update(leftSon,left,middle,position,value);
        else
            update(rightSon,middle+1,right,position,value);

        tree[node] = max(tree[leftSon],tree[rightSon]);
    }
}

int query(int node,int left,int right,int x,int height) {
    if(wall[left].x > x || tree[node] < height)
        return (0);

    if(left == right)
        return left;

    int answer;
    int middle = (left + right) >> 1;

    answer = query(rightSon,middle+1,right,x,height);

    if(!answer)
        return query(leftSon,left,middle,x,height);
    else
        return answer;
}