Submission #891531

#	Time	Username	Problem	Language	Result	Execution time	Memory
891531		Muhammad_Aneeq	Rectangles (IOI19_rect)	C++17	25 / 100	5026 ms	268120 KiB

rect

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <vector>
#include <iostream>
using namespace std;
long long const N=2600;
long long pre[N][N]={};
struct segt
{
  vector<long long>a;
  long long seg[4*N];
  segt(vector<int>&s)
  {
    a={begin(s),end(s)};
    build(1,0,a.size()-1);
  } 
  void build(long long i,long long st,long long en)
  {
    if (st==en)
    {
      seg[i]=a[st];
      return;
    }
    long long mid=(st+en)/2;
    build(i*2,st,mid);build(i*2+1,mid+1,en);
    seg[i]=max(seg[i*2],seg[i*2+1]);
  }
  long long get(long long i,long long l,long long r,long long st,long long en)
  {
    if (st>=l&&en<=r)
      return seg[i];
    if (st>r||en<l)
      return 0;
    long long mid=(st+en)/2;
    return max(get(i*2,l,r,st,mid),get(i*2+1,l,r,mid+1,en));
  }
};
long long getpre(long long a,long long b,long long c,long long d)
{
	a++;b++;c++;d++;
	return pre[c][d]-pre[c][b-1]-pre[a-1][d]+pre[a-1][b-1];
}
segt* St[2][N]={NULL};
long long count_rectangles(vector<vector<int>>a)
{
  long long n=a.size(),m=a[0].size();
  for (long long i=0;i<n;i++)
    St[0][i]=new segt(a[i]);
  for (long long i=0;i<m;i++)
  {
    vector<int>z;
    for (long long j=0;j<n;j++)
      z.push_back(a[j][i]);
    St[1][i]=new segt(z);
  }
  bool w=0;
  for (long long i=0;i<n;i++)
  {
    for(long long j=0;j<m;j++)
      if (a[i][j]>1)
        w=1;
  }
  if (w==0)
  {
    for (long long i=1;i<=n;i++)
      for (long long j=1;j<=m;j++)
        pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i-1][j-1];
    long long ans=0;
    for (long long i=1;i<n-1;i++)
    {
      for (long long j=1;j<m-1;j++)
      {
        if (a[i][j]==0&&a[i][j-1]==1&&a[i-1][j]==1)
        {
          long long st=i,en=n;
          while (st+1<en)
          {
 			long long mid=(st+en)/2;
 			if (getpre(i,j-1,mid,j)==mid-i+1&&getpre(i,j,mid,j)==0)
 				st=mid;
 			else
 				en=mid;
          }
          if (st==n-1)
          	continue;
          long long k=st;
          st=j,en=m;
          while (st+1<en)
          {
          	long long mid=(st+en)/2;
          	if (getpre(i-1,j,i,mid)==(mid-j+1)&&getpre(i,j,k,mid)==0&&getpre(i,mid,k,mid+1)==(k-i+1)&&getpre(k,j,k+1,mid)==(mid-j+1))
          		st=mid;
          	else
          		en=mid;
          }
          if (st==m-1)
          	continue;
          long long l=st;
          if (getpre(i,j-1,k,j)==(k-i+1)&&getpre(i-1,j,i,l)==(l-j+1)&&getpre(i,j,k,l)==0&&getpre(i,l,k,l+1)==(k-i+1)&&getpre(k,j,k+1,l)==(l-j+1))
          	ans++;
        }
      }
    }
    return ans;
  }
  long long ans=0;
  for (long long i=1;i<n-1;i++)
  {
    for (long long j=1;j<m-1;j++)
    {
      for (long long k=i;k<n-1;k++)
      {
        for (long long l=j;l<m-1;l++)
        {
          bool w=0;
          for (long long o=i;o<=k&&!w;o++)
          {
            long long f=St[0][o]->get(1,j,l,0,m-1);
            if (f>=a[o][j-1]||f>=a[o][l+1])
              w=1;
          }
          for (long long o=j;o<=l&&!w;o++)
          {
            long long f=St[1][o]->get(1,i,k,0,n-1); 
            if (f>=a[i-1][o]||f>=a[k+1][o])
              w=1;
          }
          ans+=(!w);
        }
      }
    }
  }
  return ans;
}

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