Cod sursa(job #1479206)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 30 august 2015 19:07:37
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>

using namespace std;

ifstream fin("zc.in");
ofstream fout("zc.out");

const int NMax = 1300005;
const int ax[] = {0, 0, 0, 0, 0, -1, -1, -1, -2, 1, 1, 1, 2};
const int ay[] = {-2, -1, 0, 1, 2, -1, 0, 1, 0, -1, 0, 1, 0};

int ka, kb;
pair < int, int > A[NMax], B[NMax];

int bin_search(pair < int, int > P, pair < int, int > v[]){
    int lo = 1, hi = kb, mid;
    if(v[kb] <= P){
        return kb + 1;
    }
    while(lo < hi){
        mid = (lo + hi) >> 1;
        if(v[mid] > P){
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main(){
    int n, m, a, b, L, x, y, ans;
    char D;
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        fin >> a >> b;
        for(int j = 0; j < 13; j++){
            if(a + ax[j] || b + ay[j]){
                A[++ka] = make_pair(a + ax[j], b + ay[j]);
            }
        }
    }
    sort(A + 1, A + ka + 1);
    for(int i = 1; i <= ka; i++){
        if(A[i] != make_pair(B[kb].second, B[kb].first)){
            A[++kb] = A[i];
            B[kb].first = A[kb].second;
            B[kb].second = A[kb].first;
        }
    }
    sort(B + 1, B + kb + 1);
    x = y = ans = 0;
    for(int i = 1; i <= m; i++){
        fin >> D >> L;
        if(D == 'E'){
            ans += bin_search(make_pair(y, x + L), B) - bin_search(make_pair(y, x), B);
            x += L;
        }
        if(D == 'V'){
            ans += bin_search(make_pair(y, x - 1), B) - bin_search(make_pair(y, x - L - 1), B);
            x -= L;
        }
        if(D == 'N'){
            ans += bin_search(make_pair(x, y + L), A) - bin_search(make_pair(x, y), A);
            y += L;
        }
        if(D == 'S'){
            ans += bin_search(make_pair(x, y - 1), A) - bin_search(make_pair(x, y - L - 1), A);
            y -= L;
        }
    }
    fout << ans;
    return 0;
}