Cod sursa(job #1074371)

Utilizator tudorv96Tudor Varan tudorv96 Data 7 ianuarie 2014 16:50:45
Problema Zota & Chidil Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

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

map <int, vector <pair <int, int> > > MX, MY;
int n, m, xi, yi;
vector <int> vx, vy;
long long sol;

int abs(int x) {
    return (x > -x ? x : -x);
}

long long query(vector <pair <int, int> > v, int lo, int hi) {
    int poz = -1;
    for (unsigned step = (1 << 17); step; step >>= 1)
        if (poz + step < v.size() && v[poz + step].second < lo)
            poz += step;
    long long s = 0;
    for (unsigned i = poz + 1; i < v.size() && v[i].first <= hi; ++i) {
        int val;
        if (i == poz + 1)
            val = min(hi, v[i].second) - max(lo, v[i].first) + 1;
        else
            val = min(hi, v[i].second) - max(v[i].first, v[i-1].second + 1) + 1;
        if (val > 0)
            s += val;
    }
    return s;
}

int main() {
    fin >> n >> m;
    while (n--) {
        int x, y;
        fin >> x >> y;
        for (int i = -2; i <= 2; ++i) {
            MX[x+i].push_back (make_pair (y - 2 + abs(i), y + 2 - abs(i)));
            MY[y+i].push_back (make_pair (x - 2 + abs(i), x + 2 - abs(i)));
            vx.push_back (x + i);
            vy.push_back (y + i);
        }
    }
    sort (vx.begin(), vx.end());
    sort (vy.begin(), vy.end());
    int last = -1;
    for (vector <int> :: iterator it = vx.begin(); it != vx.end(); ++it)
        if (last == -1 || vx[last] != *it) {
            sort (MX[*it].begin(), MX[*it].end());
            last = it - vx.begin();
        }
    last = -1;
    for (vector <int> :: iterator it = vy.begin(); it != vy.end(); ++it)
        if (last == -1 || vy[last] != *it) {
            sort (MY[*it].begin(), MY[*it].end());
            last = it - vy.begin();
        }
    while (m--) {
        char d; int dist;
        fin >> d >> dist;
        if (d == 'S') {
            sol += query(MX[xi], yi - dist, yi);
            yi -= dist;
        }
        if (d == 'N') {
            sol += query(MX[xi], yi, yi + dist);
            yi += dist;
        }
        if (d == 'E') {
            sol += query(MY[yi], xi, xi + dist);
            xi += dist;
        }
        if (d == 'V') {
            sol += query(MY[yi], xi - dist, xi);
            xi -= dist;
        }
    }
    fout << sol;
}