제출 #550928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550928		600Mihnea	Rectangles (IOI19_rect)	C++17	100 / 100	4286 ms	264400 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);
  vector<vector<int>> cr(n),cc(m);

  function<bool(int, pair<int, int>)> has_row=[&](int i,pair<int, int> want){
    assert(0<=i&&i<n);
    int l=0,r=(int)wr[i].size()-1;
    while(l<=r){
      int m=(l+r)/2;
      if(wr[i][m]==want) return 1;
      if(wr[i][m]<want) l=m+1; else r=m-1;
    }
    return 0;
  };

  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&&a[r][stk.back()]!=a[r][c]) {
          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&&a[stk.back()][c]!=a[r][c]) {
          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());

  for(int i=n-1;i>=0;i--){
    cr[i].resize((int)wr[i].size(),1);
    if(i<n-1){
      int pt=0;
      for (int j=0;j<(int)wr[i].size();j++){
        while(pt<(int)wr[i+1].size()&&wr[i+1][pt]<wr[i][j]) pt++;
        if(pt<(int)wr[i+1].size()&&wr[i+1][pt]==wr[i][j]){
          cr[i][j]+=cr[i+1][pt];
        }
      }
    }
  }

  for(int i=m-1;i>=0;i--){
    cc[i].resize((int)wc[i].size(),1);
    if(i<m-1){
      int pt=0;
      for (int j=0;j<(int)wc[i].size();j++){
        while(pt<(int)wc[i+1].size()&&wc[i+1][pt]<wc[i][j]) pt++;
        if(pt<(int)wc[i+1].size()&&wc[i+1][pt]==wc[i][j]){
          cc[i][j]+=cc[i+1][pt];
        }
      }
    }
  }




  ll sol=0;
  for (int r1=1;r1<n-1;r1++){
    int posr=-1;
    for (auto &it:wr[r1]) {
      posr++;
      int c1=it.first,c2=it.second;

      {
        int c_smaller_or_equal=0,c_smaller=0;
        {
          int low=0,high=(int)wc[c1].size()-1;
          while(low<=high){
            int mid=(low+high)/2;
            if(wc[c1][mid].first<=r1){
              c_smaller_or_equal=mid+1;
              low=mid+1;
            }else{
              high=mid-1;
            }
          }
        }
        {
          int low=0,high=(int)wc[c1].size()-1;
          while(low<=high){
            int mid=(low+high)/2;
            if(wc[c1][mid].first<r1){
              c_smaller=mid+1;
              low=mid+1;
            }else{
              high=mid-1;
            }
          }
        }
        assert(c_smaller<=c_smaller_or_equal);
        if(c_smaller<c_smaller_or_equal){
          for (int p=c_smaller;p<c_smaller_or_equal;p++){
            auto it2=wc[c1][p];
            assert(it2.first==r1);
            int r2=it2.second;
            if(cr[r1][posr]>=r2-r1+1&&cc[c1][p]>=c2-c1+1){
              sol++;
            }
          }
        }
      }

    }

  }
  return sol;
}

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