fork(1) download 
  1. /*
  2.     File: rectangles.cpp
  3.     
  4.     Compile command: g++ -O2 -std=c++17 -Wall -Wextra -pedantic rectangles.cpp -o rectangles.o
  5.     
  6.     Example:
  7.     4 3
  8.     ###
  9.     #.#
  10.     #.#
  11.     ###
  12.     
  13.     Output: 1
  14. */
  15.  
  16. #pragma GCC diagnostic ignored "-Wunused-result"
  17. #include <stdio.h>
  18. #include <cassert>
  19. #include <cstdlib>
  20. #include <ctime>
  21. #include <cstdint>
  22.  
  23. const bool TIMING = true;
  24.  
  25. char getChar() {
  26.     static char buffer[1024*1024];
  27.     static int pos = 0;
  28.     static int size = 0;
  29.     if (pos == size) {
  30.         size = fread(buffer, 1, 1024*1024, stdin);
  31.         pos = 0;
  32.     }
  33.     if (pos == size) {
  34.         return EOF;
  35.     }
  36.     return buffer[pos++];
  37. }
  38.  
  39. void putChar(char c) {
  40. // c == -1 or size == sizeof(buffer) --> flush buffer
  41.     static char buffer[1024*1024];
  42.     static int size = 0;
  43.     if (size == 1024 * 1024 || c == -1) {
  44.         fwrite(buffer, 1, size, stdout);
  45.         size = 0;
  46.     }
  47.     buffer[size++] = c;
  48. }
  49.  
  50. int getInt(bool& success) {
  51.     char c = '?';
  52.     while (!(c == '-' || ('0' <= c && c <= '9') || c == EOF)) {
  53.         c = getChar();
  54.     }
  55.     if (c == EOF) {
  56.         success = false;
  57.         return 0;
  58.     }
  59.     int sign = 1;
  60.     if (c == '-') {
  61.         sign *= -1;
  62.         c = getChar();
  63.     }
  64.     int answ = 0;
  65.     while ('0' <= c && c <= '9') {
  66.         (answ *= 10) += (c-'0');
  67.         c = getChar();
  68.     }
  69.     success = true;
  70.     return sign * answ;
  71. }
  72.  
  73. void putStr(const char *buf) {
  74.     for (auto it = buf; *it != '\0'; ++it) {
  75.         putChar(*it);
  76.     }
  77. }
  78.  
  79. void putInt(int number) {
  80.     static char buf[12];
  81.     sprintf(buf, "%d", number);
  82.     putStr(buf);
  83. }
  84.  
  85. void putInt(long long number) {
  86.     static char buf[24];
  87.     sprintf(buf, "%lld", number);
  88.     putStr(buf);
  89. }
  90.  
  91. int main() {
  92.     double total_time = clock();
  93.     for (int id = 0; id < 100; ++id) {
  94.         int nRows = 350; // input number of rows of array
  95.         int nCols = 350; // input number of cols of array
  96.  
  97.         static char arr[350][350]; // arr[r][c] = 1 if '#' and arr[r][c] = 0 if '.'
  98.         for (int row = 0; row < nRows; ++row) {
  99.             for (int col = 0; col < nCols; ++col) {
  100.                 char c = '#'; // char c = getChar();
  101.                 arr[row][col] = (c == '#');
  102.             }
  103.             char c = '\n'; // char c = getChar();
  104.             assert(c == '\n' || (c == EOF && row == nRows-1));
  105.         }
  106.  
  107.         static int maxLenDown[351][350]; // maxLenDown[r][c] = len of max sequence of '#' from pos (row, col) in side of increasing row
  108.         for (int row = 0; row <= nRows; ++row) {
  109.             for (int col = 0; col < nCols; ++col) {
  110.                 maxLenDown[row][col] = 0;
  111.             }
  112.         }
  113.  
  114.         for (int row = nRows-1; row >= 0; --row) {
  115.             for (int col = 0; col < nCols; ++col) {
  116.                 if (arr[row][col]) {
  117.                     maxLenDown[row][col] = 1 + maxLenDown[row+1][col];
  118.                 }
  119.             }
  120.         }        
  121.  
  122.         static int bin_2[351]; // bin_2[i] = C(i, 2);
  123.         for (int i = 0; i < 351; ++i) {
  124.             bin_2[i] = i * (i-1) / 2;
  125.         }
  126.  
  127.         // Calculate all rectangles with top side = row1 and bottom side = row2 (rectangles with width = 2 will also be counted)
  128.         long long answ = 0;
  129.         for (int row1 = 0; row1 < nRows-2; ++row1) {
  130.             int temp = 0;
  131.             for (int row2 = row1+2; row2 < nRows; ++row2) {
  132.                 int len = 0;
  133.                 for (int col = 0; col < nCols; ++col) { // TO DO: speed up this cycle
  134.                     if (arr[row1][col] & arr[row2][col]) {
  135.                         len += (maxLenDown[row1][col] >= row2-row1+1);
  136.                     } else {
  137.                         temp += bin_2[len];
  138.                         len = 0;
  139.                     }
  140.                 }
  141.                 temp += bin_2[len];
  142.             }
  143.             answ += temp;
  144.         }
  145.         // Decreasing number of rectangles with width = 2
  146.         for (int col1 = 0; col1 < nCols-1; ++col1) {
  147.             const int col2 = col1+1;
  148.             int len = 0;
  149.             for (int row = 0; row < nRows; ++row) {
  150.                 if (arr[row][col1] & arr[row][col2]) {
  151.                     ++len;
  152.                 } else {
  153.                     if (len >= 3) {
  154.                         answ -= bin_2[len-1];
  155.                     }
  156.                     len = 0;
  157.                 }
  158.             }
  159.             if (len >= 3) {
  160.                 answ -= bin_2[len-1];
  161.             }
  162.         }
  163.  
  164.         putInt(answ);
  165.         putChar('\n');
  166.     }
  167.     putChar(-1);
  168.  
  169.     if (TIMING) {
  170.         total_time = (clock() - total_time) / CLOCKS_PER_SEC;
  171.         printf("----------------\ntime = %0.3f\n", total_time);
  172.     }
  173.  
  174.     return 0;
  175. }
Success #stdin #stdout 1.72s 4376KB
comments (?)
stdin 
Standard input is empty
stdout 
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
3687647076
----------------
time = 1.720
https://ideone.com/PrAmnJ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!