Cod sursa(job #543614)

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

#define maxSize 100001
#define x first
#define y second
#define leftSon (node<<1)
#define rightSon (node<<1)+1

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

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

int nrWalls,bombs;
stuff wall[maxSize];
int tree[4*maxSize];

// de cate ori s-a lovit zidul first la inaltimea second
map< pair<int,int>, int> height;

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

int main() {
    in >> nrWalls;

    int currentHeight;
    for(int i=1;i<=nrWalls;i++) {
        // latimea in inaltimea zidului
        in >> wall[i].width >> currentHeight;

        // ordonata sa este ordonata zidului precedent
        // plus latimea acestuia plus unu (distanta intre ziduri)
        wall[i].x = wall[i-1].x + wall[i-1].width + 1;

        // se introduce inaltimea sa in arborele de intervale
        update(1,1,nrWalls,i,currentHeight);
    }

    in >> bombs;

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

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

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

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

            // ordonate celului lovite (ordonata zidului plus latimea acestuia
            // minus de cate ori a fost bombardata linia resprectiva
            hitBlock = wall[targetWall].x + wall[targetWall].width - height[make_pair(targetWall,currentBomb.y)];

            out << hitBlock << " " << targetWall << " ";

            // daca ordonata celulei lovite este egala
            // cu ordonata zidului (s-a distrus un nivel intreg)
            if(hitBlock == wall[targetWall].x) {
                out << "YES\n";
                // se actualizeaza inaltimea zidului curent cu abscisa bombei minus unu
                update(1,1,nrWalls,targetWall,currentBomb.y-1);
            }
            else
                out << "NO\n";
        }
    }

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

    return (0);
}

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

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

        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;
}