Cod sursa(job #1263062)

Utilizator diana97Diana Ghinea diana97 Data 13 noiembrie 2014 21:15:46
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 100000 + 1;

int n, m;
vector < pair <int, int> > capcane, capcane2;

bool inside(int x, int y) {
    if (x < 0 || y < 0) return false;
    return true;
}

inline int modul(int x) {
    if (x > 0) return x;
    return -x;
}

void citeste() {
    f >> n >> m;
    int a, b;
    for (int i = 1; i <= n; i++) {
        f >> a >> b;
        for (int dx = -2; dx <= 2; dx++)
            for (int dy = -2; dy <= 2; dy++)
                if ((a + dx || b + dy) && (modul(dx) + modul(dy) <= 2)) {
                    capcane.push_back(make_pair(a + dx, b + dy));
                }
    }
}

int cauta_stanga(pair <int, int> loc, vector < pair <int, int> > capcane) {
    int sol = 0, st = 0, dr = capcane.size() - 1, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (capcane[m] <= loc) {sol = m + 1; st = m + 1;}
        else {dr = m - 1;}
    }
    return sol;
}

int cauta_dreapta(pair <int, int> loc, vector < pair <int, int> > capcane) {
    int sol = capcane.size(), st = 0, dr = capcane.size() - 1, m;
    while (st <= dr) {
        m = (st + dr) / 2;
        if (capcane[m] == loc) dr = m -  1;
        else if (capcane[m] >= loc) {sol = m; dr = m - 1;}
        else {st = m + 1;}
    }
    return sol;
}

void rezolva() {
    sort(capcane.begin(), capcane.end());
    capcane.resize(unique(capcane.begin() , capcane.end()) - capcane.begin());
    n = 0;
    for (int i = 1; i < capcane.size(); i++)
        if (capcane[i] != capcane[i - 1])
            capcane[++n] = capcane[i];
    capcane.resize(n + 1);
    capcane2.resize(n + 1);
    for (int i = 0; i < capcane.size(); i++) capcane2[i] = make_pair(capcane[i].second, capcane[i].first);
    sort (capcane2.begin(), capcane2.end());

    int X = 0, Y = 0, sol = 0;
    char c; int d;
    while (m--) {
        f >> c >> d;
        if (c == 'N') {
            //sol += cauta_dreapta(make_pair(X, Y + d), capcane) - cauta_stanga(make_pair(X, Y + 1), capcane);
            sol += upper_bound(capcane.begin(), capcane.end(), make_pair(X, Y + d)) -
                    upper_bound(capcane.begin(), capcane.end(), make_pair(X, Y + 1));
            Y += d;
        }
        else if (c == 'S') {
           // sol += cauta_dreapta(make_pair(X, Y - 1), capcane) - cauta_stanga(make_pair(X, Y - d), capcane);
            sol += upper_bound(capcane.begin(), capcane.end(), make_pair(X, Y - 1)) -
                    upper_bound(capcane.begin(), capcane.end(), make_pair(X, Y - d));
            Y -= d;
        }
        else if (c == 'E') {
           // sol += cauta_dreapta(make_pair(Y, X + d), capcane2) - cauta_stanga(make_pair(Y, X + 1), capcane2);
            sol += upper_bound(capcane2.begin(), capcane2.end(), make_pair(Y, X + d)) -
                    upper_bound(capcane2.begin(), capcane2.end(), make_pair(Y, X + 1));
            X += d;
        }
        else {
            //sol += cauta_dreapta(make_pair(Y, X - 1), capcane2) - cauta_stanga(make_pair(Y, X - d), capcane2);
            sol += upper_bound(capcane2.begin(), capcane2.end(), make_pair(Y, X - 1)) -
                    upper_bound(capcane2.begin(), capcane2.end(), make_pair(Y, X - d));
            X -= d;
        }
    }
    g << sol << '\n';
}

int main() {
    citeste();
    rezolva();
    return 0;
}