Submission #1321269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321269		SmuggingSpun	Rectangles (IOI19_rect)	C++20	27 / 100	1974 ms	22664 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void maximize(T& a, T b){
  if(a < b){
    a = b;
  }
}
vector<vector<int>>a;
int n, m;
namespace sub123{
  bool check(int x, int y, int u, int v){
    for(int i = x; i <= u; i++){
      for(int j = y; j <= v; j++){
        if(a[i][j] >= min({a[x - 1][j], a[u + 1][j], a[i][y - 1], a[i][v + 1]})){
          return false;
        }
      }
    }
    return true;
  }
  ll solve(){
    int ans = 0;
    for(int x = 1; x < n; x++){
      for(int y = 1; y < m; y++){
        for(int u = x; u + 1 < n; u++){
          for(int v = y; v + 1 < m; v++){
            if(check(x, y, u, v)){
              ans++;
            }
          }
        }
      }
    }
    return ans;
  }
}
namespace sub5{
  ll solve(){
    int ans = 0;
    for(int l = 1; l < m; l++){
      for(int r = l, mv = 0; r + 1 < m; r++){
        maximize(mv, a[1][r]);
        if(a[1][r] > min(a[0][r], a[2][r]) || mv >= a[1][l - 1]){
          break;
        }
        if(mv < a[1][r + 1]){
          ans++;
        }
      }
    }
    return ans;
  }
}
ll count_rectangles(vector<vector<int>>_a){
  swap(a, _a);
  if(max(n = a.size(), m = a[0].size()) <= 200){
    return sub123::solve();
  }
  if(n <= 3){
    return sub5::solve();
  }
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28