Cod sursa(job #1565675)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 11 ianuarie 2016 09:52:19
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cctype>
#define dim 8192
#define MAXN 1300010
using namespace std;
int step_count,trap_count,poz=0,k=0;
int dx[13]={0,-2,-1,-1,-1,0,0,0,0,1,1,1,2};
int dy[13]={0,0,-1,0,1,-2,-1,1,2,-1,0,1,0};
char buff[dim];
pair<int,int> ox[MAXN],oy[MAXN];
int modul(int x){
    if(x<0)
        return -x;
    return x;
}
int get_integer(){
    int answer=0,sign=1;
    while(!isdigit(buff[poz])&&buff[poz]!='-')
        if(++poz>=dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    while(isdigit(buff[poz])||buff[poz]=='-'){
        if(buff[poz]=='-')
            sign=-1;
        else
            answer=answer*10+buff[poz]-'0';
        if(++poz>=dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    return sign*answer;
}
char get_character(){
    char answer;
    while(!isupper(buff[poz]))
        if(++poz>=dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    while(isupper(buff[poz])){
        answer=buff[poz];
        if(++poz>=dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    return answer;
}
int find_trap(pair<int,int> v[MAXN],int x,int y){
    int left=1,right=k,middle;
    pair<int,int> point=make_pair(x,y);
    if(v[k]<=point)
        return k+1;
    while(left<=right){
        middle=(left+right)/2;
        if(v[middle]<=point)
            left=middle+1;
        else
            right=middle-1;
    }
    return left;
}
int main(){
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    int x,y,i,step,distance,answer=0,j,temp=0,subtract,add;
    char enter,direction;
    fread(buff,1,dim,stdin);
    trap_count=get_integer();
    step_count=get_integer();
    for(i=1;i<=trap_count;i++){
        x=get_integer();
        y=get_integer();
        for(j=0;j<13;j++)
            if(x+dx[j]!=0||y+dy[j]!=0)
                ox[++k]=make_pair(x+dx[j],y+dy[j]);
    }
    sort(ox+1,ox+k+1);
    ox[0].first=ox[1].first-1;
    for(i=1;i<=k;i++)
        if(ox[i]!=ox[i-1]){
            ox[++temp]=ox[i];
            oy[temp]=make_pair(ox[i].second,ox[i].first);
        }
    k=temp;
    sort(oy+1,oy+k+1);
    x=y=0;
    for(step=1;step<=step_count;++step){
        direction=get_character();
        distance=get_integer();
        if(direction=='N'){
            subtract=find_trap(ox,x,y);
            y+=distance;
            add=find_trap(ox,x,y);
        }
        if(direction=='S'){
            add=find_trap(ox,x,y-1);
            y-=distance;
            subtract=find_trap(ox,x,y-1);
        }
        if(direction=='E'){
            subtract=find_trap(oy,y,x);
            x+=distance;
            add=find_trap(oy,y,x);
        }
        if(direction=='V'){
            add=find_trap(oy,y,x-1);
            x-=distance;
            subtract=find_trap(oy,y,x-1);
        }
        answer=answer+add-subtract;
    }
    printf("%d",answer);
    return 0;
}