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
#include "dzialka.h"
#include "message.h"

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
  if (MyNodeId() > 0)
    return 0;
       
  const int r0 = 0;
  const int r1 = GetFieldHeight()-1;
  const int c0 = 0;
  const int c1 = GetFieldWidth() -1;


  vector<int> G(c1-c0+2);
  
  
  long long licznik = 0;
  
  for (int r = r0; r <= r1; r++) {
    stack< pair<int, int> > s;

    for (int c = c0; c <= c1+1; c++) {
       if (c <= c1 && IsUsableCell(r, c))
         G[c]++;
       else
         G[c]=0;
        
//       cout << G[c] << " | ";
        
       int ostatni = -1; 
       while(!s.empty() && s.top().second > G[c]) {
         
         
         
         licznik += (long long) (c-s.top().first) * (c-s.top().first+1)/2*s.top().second;
//         cout << "d1: " << (long long) (c-s.top().first) * (c-s.top().first+1)/2*s.top().second << endl;
           
         ostatni = s.top().first;
         s.pop();
         
         if(!s.empty()) {
           licznik -= (long long) (c-ostatni)*(c-ostatni+1)/2*s.top().second;
//                    cout << "d2: " << -(long long) (c-ostatni)*(c-ostatni+1)/2*s.top().second << endl;
           }
       }
       
       if(ostatni >= 0 && G[c]>0) {
         long long licznik0 = licznik;
         if(!s.empty())
           licznik += (long long) (c-ostatni)*(c-ostatni+1)/2*s.top().second;
         licznik -= (long long) (c-ostatni)*(c-ostatni+1)/2*G[c];
//         cout << "d3: " << licznik - licznik0 << endl;
         s.push( pair<int, int>(ostatni, G[c]) );
       }
         
       
         
       if(s.empty() || s.top().second < G[c])
         if(G[c] > 0)
           s.push( pair<int, int>(c, G[c]) );
    }
//    cout << endl << "---------- " << licznik << endl;
  }

  cout << licznik << "\n";
}