Cod sursa(job #1453368)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 23 iunie 2015 13:19:51
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

int n, m, Nr2, Nr, Ans;
pair < int, int > a[1300010], b[1300010];

int cb(int X, int Y, pair < int, int > v[]){
    int st = 1, dr = Nr, med;
    pair < int, int > val(X, Y);
    if (v[Nr] <= val)
        return Nr + 1;
    while (st < dr){
        med = (st + dr) / 2;
        if(v[med] <= val)
            st = med + 1;
        else
            dr = med;
    }
    return st;
}

int main(){
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int k = 1; k <= n; ++k){
        int A, B;
        scanf("%d %d\n", &A, &B);
        for (int i = -2; i <= 2; ++i)
            for (int j = -2; j <= 2; ++j)
                if(fabs(i) + fabs(j) <= 2 && (A + i || B + j)){
                    a[++Nr2].x = A + i;
                    a[Nr2].y = B + j;
                }
    }
    sort (a + 1, a + 1 + Nr2);
    for(int i = 1; i <= Nr2; ++i)
        if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y){
            a[++Nr] = a[i];
            b[Nr].x = a[i].y;
            b[Nr].y = a[i].x;
        }
    sort (b + 1, b + 1 + Nr);
    int Px = 0, Py = 0;
    for(int i = 1; i <= m; ++i){
        int Val, s1 = 0, s2 = 0;
        char Type;
        scanf("%c %d\n", &Type, &Val);
        if(Type == 'N'){
            s1 = cb(Px, Py, a);
            Py += Val;
            s2 = cb(Px, Py, a);
        }
        if(Type == 'S'){
            s2 = cb(Px, Py - 1, a);
            Py -= Val;
            s1 = cb(Px, Py - 1, a);
        }
        if(Type == 'E'){
            s1 = cb(Py, Px, b);
            Px += Val;
            s2 = cb(Py, Px, b);
        }
        if(Type == 'V'){
            s2 = cb(Py, Px - 1, b);
            Px -= Val;
            s1 = cb(Py, Px - 1, b);
        }
        Ans += s2 - s1;
    }
    printf("%d\n", Ans);
    return 0;
}