Cod sursa(job #2046710)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 24 octombrie 2017 00:50:07
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

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

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> ini[DIM], 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)
{
    int n, q, m = 0, k = 0;
    in >> n >> q;
    
    for (int i = 1; i <= n; ++i) {
        int x, y;
        in >> x >> y;
        
        for (int d = 0; d <= 12; ++d)
            ini[++m] = make_pair(x + dx[d], y + dy[d]);
    }
    
    sort(ini + 1, ini + m + 1);
    for (int i = 1; i <= m; ++i) {
        if (k and ini[i] == lst[0][k])
            continue;
        
        lst[0][++k] = make_pair(ini[i].first, ini[i].second);
        lst[1][  k] = make_pair(ini[i].second, ini[i].first);
    }
    
    sort(lst[0] + 1, lst[0] + k + 1);
    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;
        in >> 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(1, x, y - d, y - 1); y -= d; break;
            case 'W': ans += count(0, y, x - d, x - 1); x -= d; break;
        }
    }
    
    out << ans << endl;
    return 0;
}