Cod sursa(job #2054476)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 noiembrie 2017 23:46:18
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <cstdio>
#include <algorithm>
#define ff first
#define ss second
#define DIM 1300005
#define INF 2000000000

using namespace std;

//ifstream f("zc.in");
//ofstream g("zc.out");

int n, m, x, y, xi, yi, stanga, dreapta, stangaFin, dreaptaFin, xc, yc, cnt, val, cntx, cnty;
long long sol;

char d;

pair<int, int> capc[2][DIM];

const int dx[13] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
const int dy[13] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

int main()
{
    //InParser fin("zc.in");
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    //f>>n>>m;
    for(int i = 1; i <= n; ++ i){
        scanf("%d %d", &x, &y);
        //f>>x>>y;
        for(int ii = 0; ii < 13; ++ ii){
            xc = x + dx[ii];
            yc = y + dy[ii];
            if(xc || yc){
                capc[0][++cnt] = make_pair(xc, yc);
            }
        }
    }

    sort(capc[0] + 1, capc[0] + cnt + 1);


    for(int i = 2; i <= cnt; ++ i){
        if(capc[0][i] != capc[0][i - 1])
            capc[0][++cntx] = capc[0][i];

    }
    cnt = cntx;
    capc[0][++cnt] = make_pair(INF, INF);
    for(int i = 1; i <= cnt; ++ i)
        capc[1][i] = make_pair(capc[0][i].ss, capc[0][i].ff);
    sort(capc[1] + 1, capc[1] + cnt + 1);

    x = 0;
    y = 0;
    for(int i = 1; i <= m; ++ i){
        scanf("\n%c %d", &d, &val);
        //f>>d>>val;
        xi = x;
        yi = y;
        switch(d){
            case 'N': sol += (int)(upper_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y + val)) - lower_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y + 1))); y += val;break;
            case 'S': sol += (int)(upper_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y - 1)) - lower_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y - val))); y -= val;break;
            case 'V': sol += (int)(upper_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x - 1)) - lower_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x - val))); x -= val;break;
            case 'E': sol += (int)(upper_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x + val)) - lower_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x + 1))); x += val;break;
        }
    }

    printf("%lld\n", sol);
    //g<<sol;

    return 0;
}