Cod sursa(job #2054467)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 noiembrie 2017 23:41:18
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <fstream>
//#include <cstdio>
#include <algorithm>
#define ff first
#define ss second
#define DIM 1350005
#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> capc[2][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){
                capc[0][++cnt] = make_pair(xc, yc);
            }
        }
    }

    sort(capc[0] + 1, capc[0] + cnt + 1);


    for(int i = 2; i <= cnt; ++ i){
        if(capc[0][i].ff != capc[0][i - 1].ff || capc[0][i].ss != capc[0][i - 1].ss)
            capc[0][++cntx] = capc[0][i];

    }
    cnt = cntx;
   // capc[0][++cnt] = make_pair(INF, INF);
    for(int i = 1; i <= cnt; ++ i)
        capc[1][i] = make_pair(capc[0][i].ss, capc[0][i].ff);
    sort(capc[1] + 1, capc[1] + cnt + 1);

    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(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y + val)) - lower_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y + 1))); y += val;break;
            case 'S': sol += (int)(upper_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y - 1)) - lower_bound(capc[0] + 1, capc[0] + cnt + 1, make_pair(x, y - val))); y -= val;break;
            case 'V': sol += (int)(upper_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x - 1)) - lower_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x - val))); x -= val;break;
            case 'E': sol += (int)(upper_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x + val)) - lower_bound(capc[1] + 1, capc[1] + cnt + 1, make_pair(y, x + 1))); x += val;break;
        }
    }

    g<<sol;
    f.close();
    g.close();

    return 0;
}