#include "dzialka.h"
#include "message.h"
#include <unistd.h>
#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using i64 = int64_t;
using i32 = int32_t;

// misc {{{
template <typename T> i64 isize(const T& c) { return static_cast<i64>(c.size()); }
// }}}
// print tuples {{{
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& t) {
    return os << '[' << t.first << ',' << t.second << ']';
}
// }}}
// print containers {{{
template <typename It>
void print(ostream& os, It begin, It end, u64 len, u64 limit = 30) {
    u64 count = 0;
    os << "{";
    while (begin != end && count < limit) {
        os << "(" << *begin << ")";
        count++;
        begin++;
    }
    if (begin != end)
        os << "... " << len << " total";
    os << "}";
}
#define MAKE_PRINTER_1(container) \
template <typename T> ostream& operator<<(ostream& os, const container<T>& t) { print(os, t.begin(), t.end(), t.size()); return os; }
#define MAKE_PRINTER_2(container) \
template <typename T1, typename T2> \
ostream& operator<<(ostream& os, const container<T1, T2>& t) { \
    print(os, t.begin(), t.end(), t.size()); \
    return os; \
}
MAKE_PRINTER_1(vector)
MAKE_PRINTER_2(map)
MAKE_PRINTER_1(set)
MAKE_PRINTER_2(unordered_map)
MAKE_PRINTER_1(unordered_set)
#undef MAKE_PRINTER_1
#undef MAKE_PRINTER_2
// }}}
// read/write {{{
template <typename T> T read() { T e; cin >> e; return e; }
void read() {}
template <typename T, typename ...Ts> void read(T& v, Ts& ...ts) { v = read<T>(); read(ts...); }
template <typename T> vector<T> readv(u64 n) { vector<T> v; for (u64 i = 0; i < n; i++) v.push_back(read<T>()); return v; }
template <typename T> struct identity { const T& operator()(const T& t) const { return t; } };
#define PRINTERS(FNAME, OUTP) \
    template <typename T> void FNAME(const T& t) { OUTP << t << ' '; } \
    void FNAME##ln() { OUTP << '\n'; } \
    template <typename T> void FNAME##ln(const T& t) { OUTP << t << '\n'; } \
    template <typename T, typename F = identity<typename T::value_type>> \
    void FNAME##v(const T& t, F f = F()) { for (const auto& e : t) FNAME(f(e)); FNAME##ln(); }
PRINTERS(print, cout)
#ifdef DEBUG_PRINTS
    PRINTERS(dprint, cerr)
#else
# define dprint(...)
# define dprintv(...)
# define dprintln(...)
#endif
/// }}}

#ifdef DEBUG_MEMORY
string getmemline() {
    FILE* file = fopen("/proc/self/status", "r");
    char line[128];

    while (fgets(line, 128, file) != NULL){
        if (strncmp(line, "VmSize:", 7) == 0){
            fclose(file);
            return line;
        }
    }
    fclose(file);
    return "";
}
void logmem() {
    dprint(getmemline());
}
#else
#define logmem(...)
#endif


bool is_blocked(i64 x, i64 y) { return !IsUsableCell(x, y); }

struct BoardData {
    BoardData() {
    }
    void init() {
        workers_ = NumberOfNodes();
        maxx_ = GetFieldHeight();
        maxy_ = GetFieldWidth();
        dprint("workers:"); dprintln(workers_);
        dprint("maxx:"); dprintln(maxx_);
        dprint("maxy:"); dprintln(maxy_);
        workers_ = min(workers_, min(maxx_, maxy_));
        for (i64 w = 0; w <= workers_; w++)
            x0s_[x0(w)] = w;
    }
    i64 workers() const { return workers_; }
    i64 maxx() const { return maxx_; }
    i64 maxy() const { return maxy_; }
    i64 x0(i64 w) const { return (w * maxx()) / workers(); }
    i64 y0(i64 w) const { return (w * maxy()) / workers(); }
    bool is_x0(i64 x) const { return x0s_.find(x) != x0s_.end(); }
    i64 x0_to_w(i64 x) const { assert(is_x0(x)); return x0s_.find(x)->second; }
private:
   i64 workers_;
   i64 maxx_;
   i64 maxy_;
   unordered_map<i64, i64> x0s_;
};
BoardData board;

struct WorkerData {
    WorkerData(i64 w0 = MyNodeId()) : b_(board) {
        w_ = w0;
    }
    bool should_run() const { return w_ < b_.workers(); }
    const BoardData& b() const { return b_; }
    i64 w() const { return w_; }
    i64 x0() const { return b().x0(w()); }
    i64 y0() const { return b().y0(w()); }
    i64 x1() const { return b().x0(w() + 1); }
    i64 y1() const { return b().y0(w() + 1); }
private:
    i64 w_;
    const BoardData& b_;
};

struct Heights {
    Heights(i64 xmin0, i64 ymin0, i64 xmax0, i64 ymax0)
            : xmin_(xmin0), ymin_(ymin0), xmax_(xmax0), ymax_(ymax0) {
        cur_x_ = xmax_;
        cur_hs_.resize(ymax() - ymin());
        for (i64 i = 0; i <= board.workers(); i++)
            x0_hss_.push_back(cur_hs_);
        update_x0_hss_();
        cache_x_ = -1;
#ifdef DEBUG_PRINTS
        i64 s = x0_hss_.capacity();
        for (i64 i = 0; i < isize(x0_hss_); i++)
            s += x0_hss_[i].capacity();
        dprint("Heights constructor"); dprint(s); dprint(xmin0); dprint(ymin0); dprint(xmax0); dprintln(ymax0);
#endif
    }
    i64 xmin() const { return xmin_; }
    i64 ymin() const { return ymin_; }
    i64 xmax() const { return xmax_; }
    i64 ymax() const { return ymax_; }
    i64& h(i64 x, i64 y) {
        assert(xmin() <= x && x <= xmax());
        assert(ymin() <= y && y < ymax());
        if (x == cache_x_)
            return x0_hss_[cache_idx_][y - ymin()];
        if (board.is_x0(x)) {
            cache_idx_ = board.x0_to_w(x);
            cache_x_ = x;
            return x0_hss_[cache_idx_][y - ymin()];
        }
        dprint("wrong x:"); dprintln(x);
        assert(false);
    }
    const i64& h(i64 x, i64 y) const {
        assert(xmin() <= x && x <= xmax());
        assert(ymin() <= y && y < ymax());
        if (x == cache_x_)
            return x0_hss_[cache_idx_][y - ymin()];
        if (board.is_x0(x)) {
            cache_idx_ = board.x0_to_w(x);
            cache_x_ = x;
            return x0_hss_[cache_idx_][y - ymin()];
        }
        dprint("wrong x:"); dprintln(x);
        assert(false);
    }
    void start_sequencing() { cur_hs_ = x0_hss_[board.x0_to_w(cur_x_)]; }
    const vector<i64>& next_row() {
        // skips xmax()
        assert(cur_x_ > xmin());
        cur_x_--;
        for (i64 y = ymin(); y < ymax(); y++)
            cur_hs_[y - ymin()] = is_blocked(cur_x_, y) ? 0 : cur_hs_[y - ymin()] + 1;
        update_x0_hss_();
        return cur_hs_;
    }
    bool is_populated() const { return xmin() == cur_x_; }
    void populate_all() {
        start_sequencing();
        vector<i64> hs;
        while (!is_populated())
            (void)next_row();
    }
private:
    void update_x0_hss_() {
        if (board.is_x0(cur_x_))
            x0_hss_[board.x0_to_w(cur_x_)] = cur_hs_;
    }
    const u64 xmin_, ymin_, xmax_, ymax_;
    i64 cur_x_;
    mutable i64 cache_x_;
    mutable i64 cache_idx_;
    vector<i64> cur_hs_;
    vector<vector<i64>> x0_hss_;
};

Heights init_heights_after(const WorkerData& worker) {
    return Heights(worker.x0(), 0, worker.x1(), worker.b().maxy());
}

struct HeightsReceiver {
    HeightsReceiver(Heights& heights, const WorkerData& worker) :
        h_(heights)
    {
        for (i64 i = 0; i < board.workers(); i++)
            remaining_.push_back(board.y0(i + 1) - board.y0(i));
        remaining_[worker.w()] = 0;
    }
    void add(i64 w, i64 value) {
        const i64 y = board.y0(w + 1) - remaining_[w];
        h_.h(h_.xmax(), y) = value;
        assert(remaining_[w]);
        remaining_[w]--;
    }
    i64 remaining(i64 w) const {
        return remaining_[w];
    }
    bool complete() const {
        for (i64 i = 0; i < board.workers(); i++)
            if (remaining(i))
                return false;
        return true;
    }
private:
    Heights& h_;
    vector<i64> remaining_;
};

struct HeightsSender {
    HeightsSender(const Heights& heights, const WorkerData& worker) :
        h_(heights)
    {
        for (i64 i = 0; i < board.workers(); i++)
            remaining_.push_back(worker.y1() - worker.y0());
        remaining_[worker.w()] = 0;
    }
    i64 pull(i64 w) {
        assert(remaining_[w]);
        const i64 y = h_.ymax() - remaining_[w];
        assert(remaining_[w]);
        remaining_[w]--;
        return h_.h(board.x0(w + 1), y);
    }
    i64 remaining(i64 w) const {
        return remaining_[w];
    }
    bool complete() const {
        for (i64 i = 0; i < board.workers(); i++)
            if (remaining(i))
                return false;
        return true;
    }    
private:
    const Heights h_;
    vector<i64> remaining_;
};

struct Item {
    i64 h, y, area;
};

i64 calc_res(const vector<i64>& hs) {
    u64 res = 0;
    vector<Item> qu;
    qu.push_back(Item{-1, -1, 0});
    for (i64 i = 0; i < isize(hs); i++) {
        assert(!qu.empty());
        while (qu.back().h >= hs[i])
            qu.pop_back();
        qu.push_back(Item{hs[i], i, qu.back().area + (i - qu.back().y) * hs[i]});
        res += qu.back().area;
    }
    return res;
}

i64 calc_res(Heights& heights) {
//    dprintln("showing my hss (before calc_res):");
//#ifdef DEBUG_PRINTS
//    for (i64 y = heights.ymin(); y < heights.ymax(); y++)
//        dprint(heights.h(heights.xmax(), y));
//    dprintln();
//#endif
    heights.start_sequencing();
    i64 res = 0;
    while (!heights.is_populated()) {
        const auto& hs = heights.next_row();
//        dprint("next row:"); dprintln(hs);
        res += calc_res(hs);
    }
    return res;
}

const auto MAX_IN_MESSAGE = (1 << 14) - 30;

void exchange_hss(const WorkerData& worker, const Heights& inp_hss, Heights& outp_hss) {
    for (i64 y = worker.y0(); y < worker.y1(); y++)
        outp_hss.h(worker.x1(), y) = inp_hss.h(worker.x1(), y);
//    dprintln("showing my hss:");
//#ifdef DEBUG_PRINTS
//    for (i64 w = 0; w <= board.workers(); w++) {
//        dprint("x ="); dprintln(board.x0(w));
//        for (i64 y = inp_hss.ymin(); y < inp_hss.ymax(); y++)
//            dprint(inp_hss.h(board.x0(w), y));
//        dprintln();
//    }
//#endif
    HeightsSender sender(inp_hss, worker);
    HeightsReceiver receiver(outp_hss, worker);
    while (!sender.complete() || !receiver.complete()) {
        for (i64 w = 0; w < board.workers(); w++) {
            if (sender.remaining(w)) {
//                dprint("sending to"); dprint(w); dprint(":");
                for (i64 i = 0; i < MAX_IN_MESSAGE; i++) {
                    if (!sender.remaining(w))
                        break;
                    const auto x = sender.pull(w);
//                    dprint(x);
                    PutInt(w, static_cast<i32>(x));
                }
//                dprintln();
                Send(w);
            }
            if (receiver.remaining(w)) {
//                dprint("receiving from"); dprint(w); dprint(":");
                Receive(w);
                for (i64 i = 0; i < MAX_IN_MESSAGE; i++) {
                    if (!receiver.remaining(w))
                        break;
                    const auto x = static_cast<i64>(GetInt(w));
//                    dprint(x);
                    receiver.add(w, x);
                }
//                dprintln();
            }
        }
    }
}

void send_result(i64 res) {
    PutLL(0, res);
    Send(0);
}

i64 receive_res() {
    i64 res = 0;
    for (i64 i = 1; i < board.workers(); i++) {
        Receive(i);
        res += GetLL(i);
    }
    return res;
}

void solve_many_cores(const WorkerData& worker) {
    logmem();
    Heights hss_before(0, worker.y0(), board.maxx(), worker.y1());
    hss_before.populate_all();
    dprintln("first heights initialized");
    logmem();
    Heights hss(worker.x0(), 0, worker.x1(), board.maxy());
    dprintln("second heights initialized");
    logmem();
    exchange_hss(worker, hss_before, hss);
    dprintln("heights exchanged");
    logmem();
    const i64 local_res = calc_res(hss);
    logmem();
    dprint("local res: "); dprintln(local_res);
    if (worker.w() != 0)
        send_result(local_res);
    else {
        const i64 global_res = local_res + receive_res();
        cout << global_res << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    board.init();
    WorkerData w;
    logmem();
    if (w.should_run())
        solve_many_cores(w);
}