Cod sursa(job #2930470)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 28 octombrie 2022 15:24:40
Problema Zota & Chidil Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <bits/stdc++.h>

using namespace std;

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

#define int long long

struct punct
{
    int x,y;
};

vector<punct>lin,col;
vector<pair<signed,signed>>aux;
int n,m;
const int dl[] = {-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
const int dc[] = {0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
long long ans;

bool cmpl(punct A,punct B)
{
    if (A.y != B.y)
        return A.y < B.y;
    else
        return A.x < B.x;
}

bool cmpc(punct A,punct B)
{
    if (A.x != B.x)
        return A.x < B.x;
    else
        return A.y < B.y;
}

int bsc(int l,int c)
{
    int st = -1,pas = 1 << 20;
    while (pas != 0)
    {
        if (st + pas < col.size() and (col[st + pas].x < l or (col[st + pas].x == l and col[st + pas].y <= c)))
            st += pas;
        pas /= 2;
    }
    return st + 1;
}

int bsl(int c,int l)
{
    int st = -1,pas = 1 << 20;
    while (pas != 0)
    {
        if (st + pas < lin.size() and (lin[st + pas].y < c or (lin[st + pas].y == c and lin[st + pas].x <= l)))
            st += pas;
        pas /= 2;
    }
    return st + 1;
}

void remake_lin()
{
    aux.clear();
    aux.push_back({lin[0].x,lin[0].y});
    for (int i = 1; i < lin.size(); i++)
        if (lin[i].x != lin[i - 1].x or lin[i].y != lin[i - 1].y)
            aux.push_back(make_pair(lin[i].x,lin[i].y));
    lin.clear();
    punct auxi;
    for (int i = 0; i < aux.size(); i++)
    {
        auxi.x = aux[i].first;
        auxi.y = aux[i].second;
        lin.push_back(auxi);
    }
}

void remake_col()
{
    aux.clear();
    aux.push_back({col[0].x,col[0].y});
    for (int i = 1; i < lin.size(); i++)
        if (col[i].x != col[i - 1].x or col[i].y != col[i - 1].y)
            aux.push_back(make_pair(col[i].x,col[i].y));
    col.clear();
    punct auxi;
    for (int i = 0; i < aux.size(); i++)
    {
        auxi.x = aux[i].first;
        auxi.y = aux[i].second;
        col.push_back(auxi);
    }
}

signed main()
{
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x,y;
        in >> x >> y;
        punct aux;
        for (int j = 0; j < 13; j++)
        {
            aux.x = x + dc[j];
            aux.y = y + dl[j];
            lin.push_back(aux);
            col.push_back(aux);
        }
    }
    sort(lin.begin(),lin.end(),cmpl);
    sort(col.begin(),col.end(),cmpc);
    remake_lin();
    remake_col();
    int x = 0,y = 0;
    while (m--)
    {
        char ch;
        int s;
        in >> ch >> s;
        if (ch == 'N')
        {
            int st = y,dr = y + s;
            int nr1 = bsc(x,st),nr2 = bsc(x,dr);
            ans += (nr2 - nr1);
            y += s;
        }
        else if (ch == 'S')
        {
            int dr = y - 1,st = y - s - 1;
            int nr1 = bsc(x,st),nr2 = bsc(x,dr);
            ans += (nr2 - nr1);
            y -= s;
        }
        else if (ch == 'E')
        {
            int st = x,dr = x + s;
            int nr1 = bsl(y,st),nr2 = bsl(y,dr);
            ans += (nr2 - nr1);
            x += s;
        }
        else
        {
            int dr = x - 1,st = x - s - 1;
            int nr1 = bsl(y,st),nr2 = bsl(y,dr);
            ans += (nr2 - nr1);
            x -= s;
        }
    }
    out << ans;
    return 0;
}