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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include<ios>
#include<iostream>
#include<stack>

#include"message.h"
#include"dzialka.h"

using namespace std;

/** Czy wyświetlać komunikaty */
const bool logging=false;

int width;
int height;

/** Pamięc na historgram */
int hist[75002];
/** Informacja o tym, czy histogram był resetowany dla danego wiersza */
bool histReset[75002];

/** Odebrany fragment histogramu */
int received[75002];

/** Stos do przechowywania danych */

/** Aktualizacja histogramu dla zadanej kolumny */
void updateHist(int col) {
	for(int y=0;y<height;++y) {
		if(IsUsableCell(y, col)) {
			hist[y+1]++;
		} else {
			hist[y+1]=0; histReset[y+1]=true;
		}
	}
}

stack<int> st;

/** Funkcja licząca wszystkie prostokąty w danym (aktualnym) histogramie */
uint64_t calcRectangles() {
	uint64_t res=0;
    const int limit=height+2;   // +2 bo są terminatory
	int i = 1;

    st.push(0);
	 
	while (i < limit) {
		if (hist[st.top()] <= hist[i]) {
			st.push(i++);
		} else {
			int t = st.top(); st.pop();
			int thisHeight=hist[t];         // wysokość tego prostokąta
			int64_t thisWidth=i-(st.top()+1);   // szerokość tego prostokąta
            int nextHeight=max(hist[st.top()],hist[i]);  // wysokość kolejnego prostokąta

            int64_t dist=(thisHeight-nextHeight);
            res+= ((dist+thisWidth*dist)*thisWidth)/2;
		}
	}
	// pozostałe na stosie mniejsze prostokąty
	while(!st.empty()) st.pop();
	return res;
}

int main(int argv, char** argc) {
    uint64_t total=0;
    width=GetFieldWidth();
    height=GetFieldHeight();
    const uint64_t area=(uint64_t)width * (uint64_t)height;

	// Dla małych danych wykonujemy algorytm na jednym komputerze, aby narzut nie był zbyt duży
	// oraz jest to też obejście na warunki dla małych danych (np. GetFieldWidth==1 lub GetFieldHeight==1
//    if(width<NumberOfNodes())
	if(area<7500000)
    {
		if(MyNodeId()!=0) return 0;	// małe dane liczy tylko pierwszy
		if(logging) cerr<<"Small data processing"<<endl;

        for(int y=0;y<height+2;++y) { histReset[y]=false; hist[y]=0; }	// zerujemy pamięć dla histogramu
		for(int x=width-1;x>=0;--x) {
			updateHist(x);	// aktualizujemy histogram o daną kolumne

			total+=calcRectangles();
		}
		cout<<total<<endl;
		return 0;
	}
	// Jeżeli danych jest więcej, czyli 7500000/75000 = min width 100, a więc dla jednego komputera będzie więcej niż 1

    /** Ilość virtualnych komputerów/części */
    int virtualNodes=NumberOfNodes();
    // tak aby jedna porcja danych nie przekraczałą 7 mln operacji (daje to max 1000 virtualnych nodów)
//    while (area/virtualNodes>7000000) virtualNodes+=NumberOfNodes();

    /** Ilosc zadan dla jednego noda */
    const int part=(width+virtualNodes-1)/virtualNodes;

    int messagesSend=0;
    int dataSend=0;

    // Wykonujemy paczkami od końca
    for(int myNodeId=virtualNodes-NumberOfNodes()+MyNodeId();myNodeId>=0;myNodeId-=NumberOfNodes()) {

        /** Poczatek zakresu do przetworzenia */
        const int from = part * myNodeId;
        /** Koniec zakresu do przetworzenia */
        int to = from + part;
        if (to > width) to = width;    // ostatni fragment moze byc mniejszy

        for(int y=0;y<height+2;++y) { histReset[y]=false; hist[y]=0; }	// zerujemy pamięć dla histogramu

        // Etap 1 - Kazdy z komputerow ostatni histogram dla swojej częsci
        for (int x = to - 1; x >= from; --x) updateHist(x);

        // po tych operacjach mamy już histogram dla najbardziej lewej kolumny
        if (myNodeId + 1 < virtualNodes) {    // odbieramy dane od komputerów mających poprzednie dane
            const int source = (myNodeId + 1) % NumberOfNodes();
            if(logging) cerr<<"Wait for data from "<<(myNodeId+1)<<" ("<<source<<")"<<endl;
            Receive(source);
            for (int y = 1; y <= height; ++y) received[y] = GetInt(source);

            // Uwzględniamy odebrane dane w loklanym histogramie
            for (int y = 1; y <= height; ++y)
                if (!histReset[y]) hist[y] += received[y];    // tylko gdy nie było resetowania
        }

        if (myNodeId > 0) {    // wysyłamy dane do kolejnego noda
            const int target = (myNodeId - 1) % NumberOfNodes();
            ++messagesSend; dataSend+=sizeof(int)*height;
            if(logging) cerr<<"Sending part data to "<<(myNodeId-1)<<" ("<<target<<")"<<" total messages: "<<messagesSend<<" ("<<dataSend<<" bytes)"<<endl;
            for (int y = 1; y <= height; ++y) PutInt(target, hist[y]);
            Send(target);
        }

        // Etap 2 - jak już przesłaliśmy cząstkowe dane, to możemy zająć się obliczaniem swojego fragmentu
        if (myNodeId + 1 == virtualNodes) {
            for (int y = 1; y <= height; ++y) hist[y] = 0;    // resetujemy histogram
        } else {
            for (int y = 1; y <= height; ++y) hist[y] = received[y];    // ostawiamy na odebrany
        }

        if (logging) cerr << "Processing part "<<from<<"-"<<to<< endl;

        for (int x = to - 1; x >= from; --x) {
            updateHist(x);    // aktualizujemy histogram o daną kolumne
            total += calcRectangles();    // liczymy prostokąty na aktualnym histogramie
        }
        if (logging) cerr << "Processing done "<<from<<"-"<<to<< endl;
    }

    // Etap 3 - wysłanie wyników do pierwszego komputera, aby zsumował i wyświelił wynik;
    if(MyNodeId()==0) {
        for(int i=NumberOfNodes()-1;i>=1;--i) {
            Receive(i);
            uint64_t part=GetLL(i);
            total+=part;
        }
        cout<<total<<endl;
    } else {	// jeżeli nie pierwszy to wysyłamy wyniki do pierwszego
        PutLL(0, total);
        Send(0);
    }


	return 0;
}