Cod sursa(job #541797)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 25 februarie 2011 14:29:56
Problema Walls Scor 20
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 2.94 kb
#include<stdio.h>
#include<vector>
using namespace std;

#define maxim(a,b) (a>b ? a : b)
#define pi pair<int,int>
#define x first
#define y second
#define mp make_pair

pi v[100006];
vector < pi > s[100006];
int n,m,A[300005];

void update(int n,int st,int dr,int poz,int val)
{
    if(st==dr)
    {
        A[n]=val;
        return ;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(2*n,st,mij,poz,val);
    else
        update(2*n+1,mij+1,dr,poz,val);
    A[n]=maxim(A[2*n],A[2*n+1]);
}

int query(int n,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
        return A[n];
    int mij=(st+dr)/2;

    int s1=-1,s2=-1;
    
    if(a<=mij)
        s1=query(2*n,st,mij,a,b);
    if(b>mij)
        s2=query(2*n+1,mij+1,dr,a,b);
        
    return maxim(s1,s2);
}

int query2(int n,int st,int dr,int a,int b,int val)
{
    int mij=(st+dr)/2,s1=-1,s2=-1;
    if(a<=st && dr<=b)
    {
        if(st==dr)
        {
            if(A[n]>=val)
                return st;
            return -1;
        }
        if(A[2*n+1]>=val)
            return query2(2*n+1,mij+1,dr,a,b,val);
        if(A[2*n]>=val)
            return query2(2*n,st,mij,a,b,val);
        return -1;
    }
    if(b>mij)
        s2=query2(2*n+1,mij+1,dr,a,b,val);
    if(a<=mij)
        s1=query2(2*n,st,mij,a,b,val);
    if(s2==-1 && s1==-1)
        return -1;
    if(s2!=-1)
        return s2;
    return s1;
}

int main ()
{
    int i,j,st,dr,mij,lim;
    int val,sol,a,b,poz;
    
    freopen("walls.in","r",stdin);
    freopen("walls.out","w",stdout);
    scanf("%d",&n);
    poz=1;
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&a,&b);
        v[i].x=poz;
        v[i].y=poz+a-1;
        poz+=a+1;
        update(1,1,n,i,b);
    }
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        st=1;dr=n;sol=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij].y>=a)
                dr=mij-1;
            else
            {
                st=mij+1;
                sol=mij;
            }
        }
        if(!sol)
        {
            printf("MISS\n");
            continue;
        }
        val=query(1,1,n,1,sol);
        if(val<b)
        {
            printf("MISS\n");
            continue;
        }
        printf("HIT ");
        val=query2(1,1,n,1,sol,b);
        lim=s[val].size();
        for(j=0;j<lim;j++)
            if(s[val][j].x==b)
            {
                s[val][j].y--;
                printf("%d %d ",v[val].x+s[val][j].y,val);
                if(!s[val][j].y)
                    update(1,1,n,val,b-1);
                break;
            }
        if(j==lim)
        {
            s[val].push_back(mp(b,v[val].y-v[val].x));
            printf("%d %d ",v[val].y,val);
        }
        if(!s[val][j].y)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}