Cod sursa(job #2925504)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 15 octombrie 2022 14:48:45
Problema Zota & Chidil Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector<pair<int,int>>vl,vc;
vector<pair<int,int>>aux;

int main()
{
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int x,y;
        in >> x >> y;
        vl.push_back({x,y});
        vl.push_back({x + 1,y});
        vl.push_back({x + 2,y});
        vl.push_back({x - 1,y});
        vl.push_back({x - 2,y});
        vl.push_back({x + 1,y + 1});
        vl.push_back({x + 1,y - 1});
        vl.push_back({x - 1,y + 1});
        vl.push_back({x - 1,y - 1});
        vl.push_back({x,y + 1});
        vl.push_back({x,y + 2});
        vl.push_back({x,y - 1});
        vl.push_back({x,y - 2});
        vc.push_back({y,x});
        vc.push_back({y + 1,x});
        vc.push_back({y + 2,x});
        vc.push_back({y - 1,x});
        vc.push_back({y - 2,x});
        vc.push_back({y + 1,x + 1});
        vc.push_back({y + 1,x - 1});
        vc.push_back({y - 1,x + 1});
        vc.push_back({y - 1,x - 1});
        vc.push_back({y,x + 1});
        vc.push_back({y,x + 2});
        vc.push_back({y,x - 1});
        vc.push_back({y,x - 2});
    }
    sort(vl.begin(),vl.end());
    sort(vc.begin(),vc.end());
    aux.push_back(vl[0]);
    for (int i = 1; i < vl.size(); i++)
        if (vl[i] != vl[i - 1])
            aux.push_back(vl[i]);
    vl = aux;
    aux.clear();
    aux.push_back(vc[0]);
    for (int i = 1; i < vc.size(); i++)
        if (vc[i] != vc[i - 1])
            aux.push_back(vc[i]);
    vc = aux;
    aux.clear();
    int lin = 0,col = 0;
    long long total = 0;
    for (int i = 1; i <= m; i++)
    {
        char D;
        int x;
        in >> D >> x;
        if (D == 'N' or D == 'S')
        {
            int st,dr;
            if (D == 'N')
                dr = lin + x,st = lin,lin += x;
            else
                st = lin - x,dr = lin,lin -= x;
            int ll = -1,dd = -1;
            int pas = 1 << 20;
            while (pas != 0)
            {
                if (ll + pas < vl.size() and (vl[ll + pas].first < col or (vl[ll + pas].first == col and vl[ll + pas].second <= st)))
                    ll += pas;
                pas /= 2;
            }
            pas = 1 << 20;
            while (pas != 0)
            {
                if (dd + pas < vl.size() and (vl[dd + pas].first < col or (vl[dd + pas].first == col and vl[dd + pas].second <= dr)))
                    dd += pas;
                pas /= 2;
            }
            total += (dd - ll);
        }
        else
        {
            int st,dr;
            if (D == 'E')
                st = col,dr = col + x,col += x;
            else
                st = lin - x,dr = lin,col -= x;
            int ll = -1,dd = -1;
            int pas = 1 << 20;
            while (pas != 0)
            {
                if (ll + pas < vc.size() and (vc[ll + pas].first < lin or (vc[ll + pas].first == lin and vc[ll + pas].second <= st)))
                    ll += pas;
                pas /= 2;
            }
            pas = 1 << 20;
            while (pas != 0)
            {
                if (dd + pas < vc.size() and (vc[dd + pas].first < lin or (vc[dd + pas].first == lin and vc[dd + pas].second <= dr)))
                    dd += pas;
                pas /= 2;
            }
            total += (dd - ll);
        }
    }
    out << total;
    return 0;
}