1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <algorithm>
#include <iostream>
#include "teatr.h"
#include "message.h"

typedef long long ll;

using namespace std;

int main() {
  int nodeID = MyNodeId();
  int n = GetN();
  ll total = 0;

  int a = nodeID / 10;
  int b = nodeID % 10;
  if (a > b) {
  } else if (a == b) {
    ll begin = ((ll)n) * a / 10;
    ll end = ((ll)n) * (a+1) /10;
    if (end > begin) {
      ll count = end - begin;
      int *rows = new int[count];
      int *buffer = new int[count];
      for (ll i = begin; i < end; i++) {
        rows[i - begin] = GetElement(i);
      }
      ll base = 1;
      while(base < count) {
        for (ll step = 0; step < (count / 2 / base + 1); step++) {
          ll left_begin = min(step * 2 * base, count);
          ll mid = min((step * 2 + 1) * base, count);
          ll right_end = min((step + 1) * 2 * base, count);
          ll left_pos = left_begin;
          ll right_pos = mid;
          ll buffer_pos = left_begin;
          while (left_pos < mid && right_pos < right_end) {
            if (rows[left_pos] > rows[right_pos]) {
              total += mid - left_pos;
              buffer[buffer_pos++] = rows[right_pos++];
            } else {
              buffer[buffer_pos++] = rows[left_pos++];
            }
          }
          while (left_pos < mid) {
            buffer[buffer_pos++] = rows[left_pos++];
          }
          while (right_pos < right_end) {
            buffer[buffer_pos++] = rows[right_pos++];
          }
        }
        swap(rows, buffer);
        base *= 2;
      }
      delete[] rows;
      delete[] buffer;
    }
  } else /* if (a < b) */ {
    ll a_begin = ((ll)n) * a / 10;
    ll a_end = ((ll)n) * (a+1) /10;
    ll b_begin = ((ll)n) * b / 10;
    ll b_end = ((ll)n) * (b+1) /10;
    if (a_begin < a_end && b_begin < b_end) {
      ll lower_count = a_end - a_begin;
      ll upper_count = b_end - b_begin;
      int *lower = new int[lower_count];
      int *upper = new int[upper_count];
      for (ll i = a_begin; i < a_end; i++) {
        lower[i-a_begin] = GetElement(i);
      }
      for (ll i = b_begin; i < b_end; i++) {
        upper[i-b_begin] = GetElement(i);
      }
      sort(lower, lower+lower_count);
      sort(upper, upper+upper_count);
      ll lower_pos = 0;
      ll upper_pos = 0;
      while (lower_pos < lower_count && upper_pos < upper_count) {
        if (lower[lower_pos] > upper[upper_pos]) {
          total += lower_count - lower_pos;
          upper_pos++;
        } else {
          lower_pos++;
        }
      }
      delete[] lower;
      delete[] upper;
    }
  }

  // Accumulate and print
  if (nodeID == 0) {
    for (int i = 1; i < NumberOfNodes(); i++) {
      Receive(i);
      total += GetLL(i);
    }
    cout << total << endl;
  } else {
    PutLL(0, total);
    Send(0);
  }
  return 0;
}