Cod sursa(job #2046714)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 octombrie 2017 01:09:28
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>
using namespace std;

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};

const int DIM = 1300005;

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

int lim;
int count(int k, int p, int l, int r)
{
    return (int) (upper_bound(lst[k] + 1, lst[k] + lim + 1, make_pair(p, r)) -
                  lower_bound(lst[k] + 1, lst[k] + lim + 1, make_pair(p, l)));
}

int main(void)
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);
    
    int n, q, m = 0, k = 0;
    scanf("%d %d", &n, &q);
    
    for (int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        
        for (int d = 0; d <= 12; ++d)
            if (x + dx[d] or y + dy[d])
                lst[0][++m] = make_pair(x + dx[d], y + dy[d]);
    }
    
    sort(lst[0] + 1, lst[0] + m + 1);
    for (int i = 1; i <= m; ++i) {
        if (k and lst[0][i] == lst[0][k])
            continue;
        
        lst[0][++k] = make_pair(lst[0][i].first, lst[0][i].second);
        lst[1][  k] = make_pair(lst[0][i].second, lst[0][i].first);
    }
    
    sort(lst[1] + 1, lst[1] + k + 1);
    long long ans = 0; lim = k;
    
    for (int x = 0, y = 0; q; --q) {
        char ch; int d;
        scanf("\n%c %d", &ch, &d);
        
        switch (ch) {
            case 'N': ans += count(0, x, y + 1, y + d); y += d; break;
            case 'E': ans += count(1, y, x + 1, x + d); x += d; break;
            case 'S': ans += count(0, x, y - d, y - 1); y -= d; break;
            case 'V': ans += count(1, y, x - d, x - 1); x -= d; break;
        }
    }
    
    printf("%lld\n", ans);
    return 0;
}