Cod sursa(job #2148722)

Utilizator uniculrobyrobertoManea Robert uniculrobyroberto Data 1 martie 2018 22:18:59
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define PII pair<int,int>
#define mp make_pair
#define pb push_back
vector<PII> v,u;
int N, M, n, X, Y, sol;

void read();
int abs(int k)
{
    if(k < 0)return -k;
    return k;
}
void solve();
void write();

int main()
{
    read();
    solve();
    write();
    return 0;
}

void read()
{
    int x, y;
    freopen("zc.in", "r", stdin );
    scanf("%d%d", &N, &M );
    for(int i = 1 ; i <= N ; ++i )
    {
        scanf("%d%d\n", &x, &y );
        for(int k = -2 ; k <= 2 ; ++k )
            for(int p = -2 ; p <= 2 ; ++p )
                if(abs(k)+abs(p) <= 2 && (x+k || y+p))
                    v.pb(mp(x+k,y+p));
    }
}

void solve()
{
    char c;
    int d;
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    n = 0;
    for(int i = 1 ; i < (int)v.size() ; ++i )
        if(v[i] != v[i-1])
            v[++n] = v[i];
    v.resize(n+1);
    u.resize(n+1);
    for(int i = 0 ; i < (int)v.size() ; ++i )
        u[i] = mp(v[i].second, v[i].first);
    sort(u.begin(),u.end());
    for(int i = 1 ; i <= M ; ++i )
    {
        scanf("%c %d\n", &c, &d );
        if(c == 'N')
        {
            sol+=upper_bound(v.begin(),v.end(),mp(X,Y+d))-lower_bound(v.begin(),v.end(),mp(X,Y+1));
            Y+=d;
            continue;
        }
        if(c == 'S')
        {
            sol+=upper_bound(v.begin(),v.end(),mp(X,Y-1))-lower_bound(v.begin(),v.end(),mp(X,Y-d));
            Y-=d;
            continue;
        }
        if(c == 'E')
        {
            sol+=upper_bound(u.begin(),u.end(),mp(Y,X+d))-lower_bound(u.begin(),u.end(),mp(Y,X+1));
            X+=d;
            continue;
        }
        if(c =='V')
        {
            sol+=upper_bound(u.begin(),u.end(),mp(Y,X-1))-lower_bound(u.begin(),u.end(),mp(Y,X-d));
            X-=d;
        }
    }
}

void write()
{
    freopen("zc.out", "w", stdout );
    printf("%d", sol);
}