Submission #550868

#	Time	Username	Problem	Language	Result	Execution time	Memory
550868		600Mihnea	Rectangles (IOI19_rect)	C++17	37 / 100	5065 ms	39108 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

typedef long long ll;

ll count_rectangles(vector<vector<int>> a) {
  int n,m;
  {
    n=(int)a.size();
    assert(n>0);
    m=(int)a[0].size();
    for(int i=0;i<n;i++){
      assert((int)a[i].size()==m);
    }
  }
  vector<vector<pair<int, int>>> on_r(n);

  for (int r=0;r<n;r++){
    vector<int> stk;
    for (int c=0;c<m;c++){
      while(!stk.empty()&&a[r][stk.back()]<a[r][c]) {
        if(stk.back()+1<=c-1) {
          on_r[r].push_back({stk.back()+1, c-1});
        }
        stk.pop_back();
      }
      stk.push_back(c);
    }
    stk.clear();
    for (int c=m-1;c>=0;c--){
      while(!stk.empty()&&a[r][stk.back()]<=a[r][c]) {
        if(c+1<=stk.back()-1) {
          on_r[r].push_back({c+1, stk.back()-1});
        }
        stk.pop_back();
      }
      stk.push_back(c);
    }
    stk.clear(); /// why lol? dunno
  }

  ll sol=0;
  for (int r1=1;r1<n-1;r1++){
    for(int r2=r1;r2<n-1;r2++){
      for (auto &it:on_r[r1]) {
        int c1=it.first,c2=it.second;
        bool is_ok=1;
        for (int r=r1;r<=r2&&is_ok;r++){
          for(int c=c1;c<=c2&&is_ok;c++){
            is_ok&=(a[r][c]<a[r1-1][c]);
            is_ok&=(a[r][c]<a[r2+1][c]);
            is_ok&=(a[r][c]<a[r][c1-1]);
            is_ok&=(a[r][c]<a[r][c2+1]);
          }
        }
        sol+=is_ok;
      }
    }
  }
	return sol;
}

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