Cod sursa(job #1764928)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 26 septembrie 2016 09:10:00
Problema Walls Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <cstdio>
#include <cctype>

#define mergeala for
#define shukarime while
#define chef if
#define jale else
#define norocu inline
#define sufletu return

#define universalu void
#define salam char
#define juve int
#define daniMocanu long long
#define adiMinune short int
#define guta double

#define MOD 666019
#define MAXN 100000
#define MAXP 265000
#define BUF_SIZE 1<<17

struct mycreation{
    long long x;
    int y;
}v[MAXN+1];

daniMocanu val[MAXN+1];
juve lista[MOD], next[MAXN+1], fr[MAXN+1];
juve aint[MAXP];
juve poz, frecv, u, h;

juve pos=BUF_SIZE;
salam buf[BUF_SIZE];
FILE *fin;

norocu salam nextch(){
    chef(pos==BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos=0;
    sufletu buf[pos++];
}

norocu juve read(){
    juve x=0;
    salam ch=nextch();
    shukarime(!isdigit(ch)) ch=nextch();
    shukarime(isdigit(ch)){
        x=10*x+ch-'0';
        ch=nextch();
    }
    sufletu x;
}

norocu universalu adauga(juve x, juve y){
    daniMocanu a=((1LL*x)<<32)+y;
    juve b=a%MOD;
    juve p=lista[b];
    shukarime((p)&&(val[p]!=a)) p=next[p];
    chef(p){
        fr[p]++;
        frecv=fr[p];
    }jale{
        u++;
        fr[u]=1;
        val[u]=a;
        next[u]=lista[b];
        lista[b]=u;
        frecv=1;
    }
}

norocu juve max2(juve a, juve b){
    chef(a>b) sufletu a;
    jale sufletu b;
}

universalu defeseala(juve p, juve st, juve dr){
    chef(st==dr) aint[p]=v[st].y;
    jale{
        juve m=(st+dr)/2;
        defeseala(2*p, st, m);
        defeseala(2*p+1, m+1, dr);
        aint[p]=max2(aint[2*p], aint[2*p+1]);
    }
}

universalu zapaceala(juve p, juve st, juve dr){
    chef(st==dr) aint[p]=v[st].y;
    jale{
        juve m=(st+dr)/2;
        chef(poz<=m) zapaceala(2*p, st, m);
        jale zapaceala(2*p+1, m+1, dr);
        aint[p]=max2(aint[2*p], aint[2*p+1]);
    }
}

universalu frichineala(juve p, juve st, juve dr){
    chef(dr==poz){
        chef(aint[p]>=h){
            chef(st==dr) adauga(st, h);
            jale{
                juve m=(st+dr)/2;
                frichineala(2*p+1, m+1, dr);
                if(poz==m) frichineala(2*p, st, m);
            }
        }jale poz=st-1;
    }jale{
        juve m=(st+dr)/2;
        chef(m+1<=poz) frichineala(2*p+1, m+1, dr);
        chef(poz<=m) frichineala(2*p, st, m);
    }
}

juve main(){
    juve n, m;
    long long x;
    FILE *fout;
    fin=fopen("walls.in", "r");
    fout=fopen("walls.out", "w");
    n=read();
    v[0].x=-1;
    mergeala(juve i=1; i<=n; i++){
        v[i].x=v[i-1].x+1+read();
        v[i].y=read();
    }
    defeseala(1, 1, n);
    m=read();
    mergeala(juve i=1; i<=m; i++){
        x=read();
        h=read();
        poz=0;
        chef(x>0){
            mergeala(juve pas=1<<16; pas; pas>>=1)
                chef((poz+pas<=n)&&(v[poz+pas-1].x+1<x))
                    poz+=pas;
            frichineala(1, 1, n);
        }
        chef(poz>0){
            chef(frecv==v[poz].x-v[poz-1].x-1){
                fprintf(fout, "HIT %lld %d YES\n", v[poz].x-frecv+1, poz);
                v[poz].y=h-1;
                zapaceala(1, 1, n);
            }jale chef(v[poz].y==h) fprintf(fout, "HIT %lld %d YES\n", v[poz].x-frecv+1, poz);
            jale fprintf(fout, "HIT %lld %d NO\n", v[poz].x-frecv+1, poz);
        }jale fprintf(fout, "MISS\n");
    }
    fclose(fin);
    fclose(fout);
    sufletu 0;
}