Cod sursa(job #500929)

Utilizator cont_de_testeCont Teste cont_de_teste Data 13 noiembrie 2010 19:09:09
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cassert>

using namespace std;

#define pii 	pair<int,int>
#define ff 		first
#define ss 		second
#define maxN 	100100
#define maxM 	2000000
#define all(v) 	v.begin(), v.end()

const int di[] = { -2, -1, -1, -1,  0,  0, 0, 0, 0,  1, 1, 1, 2 } ;
const int dj[] = {  0, -1,  0,  1, -2, -1, 0, 1, 2, -1, 0, 1, 0 } ;

pii A[maxN], now, next;
vector < pii > X, Y;
int N, M, Nxy, Sol;

void baga_marfa (int x) {
    int i, j;
    for (i = 0; i <= 12; ++ i)
            if ( A[x].ff + di[i] || A[x].ss + dj[i] ) {
                X.push_back(make_pair(A[x].ff + di[i], A[x].ss + dj[i]));
                Y.push_back(make_pair(A[x].ss + dj[i], A[x].ff + di[i]));
            }
}

void do_it (int c, int val) {
    next = now;
    vector < pii > :: iterator it1, it2;
    pii tmp;

    if (c == 'N') {
        next.ss += val;
        it1 = upper_bound(all(X), now);
        it2 = upper_bound(all(X), next);
        Sol += abs(it2 - it1);
    } else if (c == 'S') {
        next.ss -= val;
        tmp = now;
        it1 = lower_bound(all(X), next);
        it2 = lower_bound(all(X), tmp);
        Sol += abs(it2 - it1);
    } else if (c == 'V') {
        next.ff -= val;
        tmp = make_pair ( next.ss, next.ff ) ;
        it1 = lower_bound(all(Y), tmp);
        tmp = make_pair ( now.ss, now.ff ) ;
        it2 = lower_bound(all(Y), tmp);
        Sol += abs(it2 - it1);
    } else {
        next.ff += val;
        tmp = make_pair ( now.ss, now.ff ) ;
        it1 = upper_bound(all(Y), tmp);
        tmp = make_pair ( next.ss, next.ff ) ;
        it2 = upper_bound(all(Y), tmp);
        Sol += abs(it2 - it1);
    }
    now = next;
}
int main () {
    int i, val;
    vector < pii > :: iterator it;
    char c;

    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);

    scanf("%d%d", &N, &M);

    for (i = 1; i <= N; ++ i) {
        scanf("%d%d", &A[i].ff, &A[i].ss);
        baga_marfa (i);
    }

    sort (X.begin(), X.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());

    sort (Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());

    for (; M -- ;) {
        scanf(" %c %d", &c, &val);
        assert(c == 'V' || c == 'E' || c == 'N' || c == 'S');
        do_it (c, val);
    }

    printf("%d\n", Sol);
}