Cod sursa(job #2711779)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 24 februarie 2021 18:18:31
Problema Zota & Chidil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, M;
long long ans;
vector<pair<int,int>> lin, col;

void add(const int &x, const int &y) {
    if(x == 0 && y == 0)
        return;
    lin.emplace_back(x, y);
}

int cbx(const int &x, const int &y) {
    int st = 0, dr = lin.size() - 1, sol = -1;
    pair<int,int> target{y, x};
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(lin[mid] <= target) {
            sol = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return sol + 1;
}

int cby(const int &y, const int &x) {
    int st = 0, dr = col.size() - 1, sol = -1;
    pair<int,int> target{x, y};
    while(st <= dr) {
        int mid = (st + dr) >> 1;
        if(col[mid] <= target) {
            sol = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }
    return sol + 1;
}

int addx(const int &x1, const int &x2, const int &y) {
    return cbx(x2, y) - cbx(x1 - 1, y);
}

int addy(const int &y1, const int &y2, const int &x) {
    return cby(y2, x) - cby(y1 - 1, x);
}

int main() {
    fin >> N >> M;
    for(int i = 0; i < N; ++i) {
        string s1, s2;
        fin >> s1 >> s2;
        int x = stoi(s1), y = stoi(s2);
		add(x - 2, y);
		add(x - 1, y - 1), add(x - 1, y), add(x - 1, y + 1);
		add(x, y - 2), add(x, y - 1), add(x, y), add(x, y + 1), add(x, y + 2);
		add(x + 1, y - 1), add(x + 1, y), add(x + 1, y + 1);
		add(x + 2, y);
    }
    sort(lin.begin(), lin.end());
    vector<pair<int,int>> aux{lin[0]};
    for(size_t i = 1; i < lin.size(); ++i)
        if(lin[i] != lin[i - 1])
            aux.emplace_back(lin[i]);
    lin = aux;
    for(const auto &x : lin)
        col.emplace_back(x.second, x.first);
    sort(col.begin(), col.end());
    int x = 0, y = 0;
    for(int pas = 0; pas < M; ++pas) {
        string op, nr;
        fin >> op >> nr;
        int adv = stoi(nr);
        if(op[0] == 'N') {
            int new_x = x + adv;
            ++x;
            ans += addx(x, new_x, y);
            x = new_x;
        }
        else
            if(op[0] == 'S') {
                int new_x = x - adv;
                --x;
                ans += addx(new_x, x, y);
                x = new_x;
            }
        else
            if(op[0] == 'E') {
                int new_y = y + adv;
                ++y;
                ans += addy(y, new_y, x);
                y = new_y;
            }
        else {
            int new_y = y - adv;
            --y;
            ans += addy(new_y, y, x);
            y = new_y;
        }
    }
    fout << ans << '\n';
}