DGCJ C++

#include <message.h>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include "gas_stations.h"

using namespace std;


#define N 5100000
#define M (2 * N)

int myVals[N];
int stackVal[M];
int stackPos[M];
int stackStart = 0, stackEnd = 0;

#define sub(x) (x == 0 ? (M - 1) : (x - 1))

void addToStack(int pos, int value) {
//  fprintf(stderr, "add to stack (%d, %d)\n", pos, value);
  while (stackEnd != stackStart && stackVal[sub(stackEnd)] > value) {
    stackEnd--;
    if (stackEnd == -1) {
      stackEnd += M;
    }
  }
  stackVal[stackEnd] = value;
  stackPos[stackEnd] = pos;
  stackEnd++;
  if (stackEnd == M) {
    stackEnd -= M;
  }
}

void removeFromStack(int pos) {
//  fprintf(stderr, "remove from stack pos = %d\n", pos);
  if (stackPos[stackStart] == pos) {
    stackStart++;
    if (stackStart == M) {
      stackStart = 0;
    }
  }
}

int main() {
  int myId = MyNodeId();
  int tankSize = (int) GetTankSize();
  int n = (int) GetNumKms();
  int nodes = NumberOfNodes();
  int len = 1 + (n - 1) / nodes;
  int left = min(n, len * myId);
  int right = min(n, len * (myId + 1));
  int myMin = (int) 2e9;
  for (int pos = left; pos < right; pos++) {
    myVals[pos - left] = (int) GetGasPrice(pos);
    myMin = min(myVals[pos - left], myMin);
  }
  for (int node = 0; node < nodes; node++) {
    PutInt(node, myMin);
    Send(node);
  }
  int allFr = max(0, (right - 1 - tankSize + 1));
  int allTo = left;
  int myRes = (int) 2e9;
  int ok = 2e9;
  for (int node = 0; node < nodes; node++) {
    Receive(node);
    int curMin = GetInt(node);
    int le = min(n, len * (node));
    int ri = min(n, len * (node + 1));
    if (le >= allFr && ri <= allTo) {
      ok = min(ok, le);
      myRes = min(myRes, curMin);
    }
  }
  long long sum = 0LL;
  int start = max(0, left - tankSize + 1);
  for (int cur = start; cur < left && cur < ok; cur++) {
    addToStack(cur, (int) GetGasPrice(cur));
  }
  for (int pos = left; pos < right; pos++) {
//    fprintf(stderr, "check pos %d\n", pos);
    addToStack(pos, myVals[pos - left]);
    removeFromStack(pos - tankSize);
//    fprintf(stderr, "my res = %d\n", myRes);
//    fprintf(stderr, "stack value = %d\n", stackVal[stackStart]);
    sum += min(myRes, stackVal[stackStart]);
  }
  PutLL(0, sum);
  Send(0);
  if (myId == 0) {
    sum = 0;
    for (int node = 0; node < nodes; node++) {
      Receive(node);
      sum += GetLL(node);
    }
    cout << sum << endl;
  }
  return 0;
}