Cod sursa(job #2054438)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 noiembrie 2017 23:03:09
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <algorithm>
#define ff first
#define ss second
#define DIM 1300005
#define INF 2000000000

using namespace std;

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

int n, m, x, y, xi, yi, stanga, dreapta, stangaFin, dreaptaFin, xc, yc, cnt, val, sol, cntx, cnty;

char d;

pair<int, int> capcx[DIM], capcy[DIM];

int dx[] = {0, 0, 1, -1, 0, 0, 1, 1, -1, -1, 2, -2, 0, 0};
int dy[] = {0, 0, 0, 0, 1, -1, 1, -1, 1, -1, 0, 0, 2, -2};

int main()
{
    f>>n>>m;
    for(int i = 1; i <= n; ++ i){
        f>>x>>y;
        for(int ii = 1; ii <= 13; ++ ii){
            xc = x + dx[ii];
            yc = y + dy[ii];
            if(xc || yc){
                capcx[++cnt] = make_pair(xc, yc);
                capcy[cnt] = make_pair(yc, xc);
            }
        }
    }

    sort(capcx + 1, capcx + cnt + 1);
    sort(capcy + 1, capcy + cnt + 1);

    for(int i = 2; i <= cnt; ++ i){
        if(capcx[i] != capcx[i - 1])
            capcx[++cntx] = capcx[i];
        if(capcy[i] != capcy[i - 1])
            capcy[++cnty] = capcy[i];

    }
    cnt = cntx;
    capcx[++cnt] = make_pair(INF, INF);
    capcy[cnt] = make_pair(INF, INF);

    x = 0;
    y = 0;
    for(int i = 1; i <= m; ++ i){
        f>>d>>val;
        xi = x;
        yi = y;
        switch(d){
            case 'N': sol += (int)(upper_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y + val)) - lower_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y + 1))); y += val;break;
            case 'S': sol += (int)(upper_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y - 1)) - lower_bound(capcx + 1, capcx + cnt + 1, make_pair(x, y - val))); y -= val;break;
            case 'V': sol += (int)(upper_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x - 1)) - lower_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x - val))); x -= val;break;
            case 'E': sol += (int)(upper_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x + val)) - lower_bound(capcy + 1, capcy + cnt + 1, make_pair(y, x + 1))); x += val;break;
        }
    }

    g<<sol;

    return 0;
}