제출 #550881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550881		600Mihnea	Rectangles (IOI19_rect)	C++17	50 / 100	5010 ms	130772 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>>> wr(n),wc(m);

  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) {
          wr[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) {
          wr[r].push_back({c+1, stk.back()-1});
        }
        stk.pop_back();
      }
      stk.push_back(c);
    }
    stk.clear(); /// why lol? dunno
  }

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

  //for(auto &V:wr) sort(V.begin(),V.end());
  //for(auto &V:wc) sort(V.begin(),V.end());

  ll sol=0;
  for (int r1=1;r1<n-1;r1++){
    for (auto &it:wr[r1]) {
      int c1=it.first,c2=it.second;
      for(auto&it2:wc[c1]){
        if(it2.first==r1){
          int r2=it2.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: 13 / 13
• Subtask 7: 0 / 28