Cod sursa(job #2711804)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 24 februarie 2021 18:41:01
Problema Zota & Chidil Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 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>> vx, vy;

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

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

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

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

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

int main() {
    fin >> N >> M;
    for(int i = 0; i < N; ++i) {
        int x, y;
        fin >> x >> y;
        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(vy.begin(), vy.end());
    vector<pair<int,int>> aux{vy[0]};
    for(size_t i = 1; i < vy.size(); ++i)
        if(vy[i] != vy[i - 1])
            aux.emplace_back(vy[i]);
    vy = aux;
    for(const auto &x : vy)
        vx.emplace_back(x.second, x.first);
    sort(vx.begin(), vx.end());
    int x = 0, y = 0;
    for(int pas = 0; pas < M; ++pas) {
        string op;
        int adv;
        fin >> op >> adv;
        if(op[0] == 'N') {
            int new_y = y + adv;
            ++y;
            ans += addy(y, new_y, x);
            y = new_y;
        }
        else
            if(op[0] == 'S') {
                int new_y = y - adv;
                --y;
                ans += addy(new_y, y, x);
                y = new_y;
            }
        else
            if(op[0] == 'E') {
                int new_x = x + adv;
                ++x;
                ans += addx(x, new_x, y);
                x = new_x;
            }
        else {
            int new_x = x - adv;
            --x;
            ans += addx(new_x, x, y);
            x = new_x;
        }
    }
    fout << ans << '\n';
}