Cod sursa(job #1074443)

Utilizator tudorv96Tudor Varan tudorv96 Data 7 ianuarie 2014 17:51:45
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <algorithm>
//#include <iostream>
using namespace std;

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

const int N = 14e5 + 5;

pair <int, int> vx[N], vy[N];
int n, m, x, y, k, kx;
long long sol;

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

int last_query(pair<int, int> v[N], pair <int, int> P) {
    int poz = -1;
    for (int step = (1 << 17); step; step >>=1)
        if (poz + step < k && v[poz + step] <= P)
            poz += step;
    //cout << P.first << " " << P.second << " " << v[poz].first << " " << v[poz].second << " " << poz << " last\n";
    return poz;
}

int first_query(pair <int, int> v[N], pair <int, int> P) {
    int poz = -1;
    for (int step = (1 << 17); step; step >>= 1)
        if (poz + step < k && v[poz + step] < P)
            poz += step;
    //cout << P.first << " " << P.second << " " << v[poz+1].first << " " << v[poz+1].second << " " << poz+1 << " first\n\n";
    return poz + 1;
}

int main() {
    fin >> n >> m;
    while (n--) {
        int x, y;
        fin >> x >> y;
        for (int i = -2; i <= 2; ++i)
            for (int j = -2; j <= 2; ++j)
                if (abs(i) + abs(j) <= 2 && (x+i || y+j))
                    vx[kx++] = make_pair (x+i, y+j);
    }
    sort (vx, vx + kx);
    for (int i = 0; i < kx; ++i)
        if (!i || vx[i] != vx[i-1])
            vx[k++] = vx[i];
    for (int i = 0; i < k; ++i)
        vy[i] = make_pair (vx[i].second, vx[i].first);
    sort (vy, vy + k);
   // for (int i = 0; i < k; ++i)
    //    cout << vx[i].first << " " << vx[i].second << "\n";
    //cout << "======\n";
   // for (int i = 0; i < k; ++i)
    //    cout << vy[i].second << " " << vy[i].first << "\n";
   // cout << "\n";
    while (m--) {
        char d; int dist;
        fin >> d >> dist;
        if (d == 'S') {
            sol += last_query(vx, make_pair(x, y)) - first_query(vx, make_pair (x, y - dist)) + 1;
            y -= dist;
        }
        if (d == 'N') {
            sol += last_query(vx, make_pair(x, y + dist)) - first_query(vx, make_pair (x, y)) + 1;
            y += dist;
        }
        if (d == 'V') {
            sol += last_query(vy, make_pair(y, x)) - first_query(vy, make_pair(y, x - dist)) + 1;
            x -= dist;
        }
        if (d == 'E') {
            sol += last_query(vy, make_pair(y, x + dist)) - first_query(vy, make_pair(y, x)) + 1;
            x +=dist;
        }
    }
    fout << sol;
}