Cod sursa(job #543668)

Utilizator vladiiIonescu Vlad vladii Data 28 februarie 2011 14:13:41
Problema Walls Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 kb
#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define maxn 100010
#define LL long long

int N, M;
int start, finish, Val, Pos;
int A[4 * maxn];
multiset<int> shots[maxn];
pair<multiset<int>::iterator,multiset<int>::iterator> ret;
struct Turn {
    LL X, H, W;
} T[maxn];

map<pair<int, int>, int> hash;

FILE *f2;

void build_aint(int nod, int left, int right) {
    if(left == right) {
         A[nod] = left;
         return;
    }

    int mij = (left + right) >> 1;
    build_aint(2*nod, left, mij);
    build_aint(2*nod+1, mij+1, right);

    if(T[ A[2*nod] ].H > T[ A[2*nod+1] ].H) {
         A[nod] = A[2*nod];
    }
    else {
         A[nod] = A[2*nod+1];
    }
}

void query(int nod, int left, int right) {
     if(start <= left && right <= finish) {
          if(T[Val].H < T[ A[nod] ].H) Val = A[nod];
          return;
     }

     int mij = (left + right) >> 1;
     if(start <= mij) query(2*nod, left, mij);
     if(mij < finish) query(2*nod+1, mij+1, right);
}

void update(int nod, int left, int right) {
     if(left == right) {
          A[nod] = Pos;
          return;
     }

     int mij = (left + right) >> 1;
     if(Pos <= mij) update(2*nod, left, mij);
     else              update(2*nod+1, mij+1, right);

    if(T[ A[2*nod] ].H > T[ A[2*nod+1] ].H) {
         A[nod] = A[2*nod];
    }
    else {
         A[nod] = A[2*nod+1];
    }
}

int cbin1(int val) {
    int sol = 0;
    int ls = 1, ld = N;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;

         if(T[mij].X + T[mij].W <= val) {
              sol = mij;
              ls = mij + 1;
         }
         else {
              ld = mij - 1;
         }
    }

    return sol;
}

void check(int x, int y) {
    int i, j, p, q;

    //aflu turnul cu coordonata T[i].X + T[i].W <= x
    int tt = cbin1(x);

    //acum aflu cel mai apropiat turn de tt din intervalul [1, tt] cu T[i].H >= y
    int incaretrag = 0;
    int ls = 1, ld = tt;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         //aflu maximul pe intervalul [mij, tt]
         start = mij, finish = tt;
         Val = 0;
         query(1, 1, N);
         int mx = Val;

         if(T[mx].H >= y) {
              //e ok
              incaretrag = mx;
              //restring intervalul
              ls = mij + 1;
         }
         else {
              //nu-i ok
              //maresc intervalul
              ld = mij - 1;
         }
    }

    if(!incaretrag) {
         fprintf(f2, "MISS\n");
         return;
    }

    //shots[incaretrag].insert(y);
    //int numar = shots[incaretrag].count(y);
    hash[ make_pair(incaretrag, y) ] ++;
    int numar = hash[ make_pair(incaretrag, y) ];

    fprintf(f2, "HIT ");
    fprintf(f2, "%d ", T[incaretrag].X + T[incaretrag].W - numar);
    fprintf(f2, "%d ", incaretrag);
    if(numar == T[incaretrag].W) {
         fprintf(f2, "YES\n");

         T[incaretrag].H = y - 1;
         Pos = incaretrag;
         update(1, 1, N);
    }
    else {
         fprintf(f2, "NO\n");
    }
}

int main() {
    FILE *f1=fopen("walls.in", "r"); f2=fopen("walls.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d\n", &N);
    LL lst = 1;
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         T[i].X = lst; T[i].W = p;
         lst = lst + p + 1;
         T[i].H = q;
    }

    build_aint(1, 1, N);

    fscanf(f1, "%d\n", &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &p, &q);

         check(p, q);
    }

    fclose(f1); fclose(f2);
    return 0;
}