제출 #226415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226415		tinjyu	Rectangles (IOI19_rect)	C++14	10 / 100	7 ms	3712 KiB

rect

#include "rect.h"
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct node{
	long long int x, y;
}array[7000000];
long long int n,m,s[705][2505][13][2],l[2505][2505],st2[2505][2505][13][2],r[2505][2505],t[10005][2],bits[20];
long long int find(int i,int j)
{
	//cout<<i<<" "<<j<<endl;
	long long int x1=st2[i][j][0][0],y1=s[i][j][0][0],x2=st2[i][j][0][1],y2=s[i][j][0][1];
	long long int le=st2[i][j][0][0]+1,ri=st2[i][j][0][1]-1;
	long long int k=log2(ri-le+1);
	//cout<<y1<<" "<<x1<<" "<<y2<<" "<<x2<<" "<<le<<" "<<ri<<endl;
	//cout<<s[y1][le][k][1]<<" "<<s[y1][ri-bits[k]+1][k][1]<<endl; 
	if( min ( s[y1][le][k][1] , s[y1][ri-bits[k]+1][k][1] ) < y2 ) return 0;
	//cout<<s[y2][le][k][0]<<" "<<s[y2][ri-bits[k]+1][k][0]<<endl;
	if( max ( s[y2][le][k][0] , s[y2][ri-bits[k]+1][k][0] ) > y1 ) return 0;

	long long int up=s[i][j][0][0]+1,down=s[i][j][0][1]-1;
	//cout<<up<<" "<<down<<endl;
	k=log2(down-up+1);
	//cout<<st2[up][x1][k][1]<<" "<<st2[down-bits[k]+1][x1][k][1]<<endl;
	if( min ( st2[up][x1][k][1] , st2[down-bits[k]+1][x1][k][1] ) < x2) return 0;
	//cout<<st2[up][x2][k][0]<<" "<<st2[down-bits[k]+1][x2][k][0]<<endl;
	if( max ( st2[up][x2][k][0] , st2[down-bits[k]+1][x2][k][0] ) > x1 )return 0;
	
	return 1;
}
bool cmp(node ax,node ay)
{
	long long int ar[10][4];
	ar[0][0]=s[ax.x][ax.y][0][0];
	ar[0][1]=st2[ax.x][ax.y][0][0];
	ar[0][2]=s[ax.x][ax.y][0][1];
	ar[0][3]=st2[ax.x][ax.y][0][1];
	ar[1][0]=s[ay.x][ay.y][0][0];
	ar[1][1]=st2[ay.x][ay.y][0][0];
	ar[1][2]=s[ay.x][ay.y][0][1];
	ar[1][3]=st2[ay.x][ay.y][0][1];
	for(int i=0;i<4;i++)
	{
		if(ar[0][i]<ar[1][i])return 1;
		if(ar[0][i]>ar[1][i])return 0;
	}
	return 0;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(int i=0;i<n;i++)
	{
		long long int p=0,st=0,en=-1;
		for(int j=0;j<m;j++)
		{
			l[i][j]=-1;
			r[i][j]=5000;
			for(int k=en;k>=st;k--)
			{
				if(a[i][j]>t[k][0])
				{
					r[i][t[k][1]]=j;
					en--;
				}
				else 
				{
					en++;
					t[en][0]=a[i][j];
					t[en][1]=j;
					if(a[i][j]<t[k][0])l[i][j]=t[k][1];
					else l[i][j]=l[i][t[k][1]];
					break;
				}
			}
			if(en==-1)
			{
				en=0;
				t[en][0]=a[i][j];
				t[en][1]=j;
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			st2[i][j][0][0]=l[i][j];
			st2[i][j][0][1]=r[i][j];
		}
	}
	for(int j=0;j<m;j++)
	{
		long long int p=0,st=0,en=-1;
		for(int i=0;i<n;i++)
		{
			s[i][j][0][0]=-1;
			s[i][j][0][1]=5000;
			for(int k=en;k>=st;k--)
			{
				if(a[i][j]>t[k][0])
				{
					s[t[k][1]][j][0][1]=i;
					en--;
				}
				else 
				{
					en++;
					t[en][0]=a[i][j];
					t[en][1]=i;
					if(a[i][j]<t[k][0])s[i][j][0][0]=t[k][1];
					else s[i][j][0][0]=s[t[k][1]][j][0][0];
					break;
				}
			}
			if(en==-1)
			{
				en=0;
				t[en][0]=a[i][j];
				t[en][1]=i;
			}
			
		}
	}
	bits[0]=1;
	for(int i=1;i<=15;i++)bits[i]=bits[i-1]*2;
	for(int k=1;bits[k-1]<=m;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(j+bits[k-1]>=m)break;
				s[i][j][k][0]=max(s[i][j][k-1][0],s[i][j+bits[k-1]][k-1][0]);
				s[i][j][k][1]=min(s[i][j][k-1][1],s[i][j+bits[k-1]][k-1][1]);
				//cout<<i<<" "<<j<<" "<<k<<" "<<st2[i][j][k][0]<<" "<<st2[i][j][k][1]<<endl;
			}
		}
	}
	for(int k=1;bits[k-1]<=n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(i+bits[k-1]>=n)break;
				st2[i][j][k][0]=max(st2[i][j][k-1][0],st2[i+bits[k-1]][j][k-1][0]);
				st2[i][j][k][1]=min(st2[i][j][k-1][1],st2[i+bits[k-1]][j][k-1][1]);
				//if(j==6)cout<<i<<" "<<j<<" "<<k<<" "<<st2[i][j][k][0]<<" "<<st2[i][j][k][1]<<endl;
			}
		}
	}
	long long int ans=0;
	long long int cnt=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(s[i][j][0][0]==-1 || s[i][j][0][1]==5000 || st2[i][j][0][0]==-1 || st2[i][j][0][1]==5000)continue;
			//if((a[i-1][j]==a[i][j] && i!=1) || (a[i][j-1]==a[i][j] && j!=1))continue;
			cnt++;
			array[cnt].x=i;
			array[cnt].y=j;
		}
	}
	sort(array+1,array+cnt+1,cmp);
	//cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++)
	{
		long long int x=array[i].x,y=array[i].y,x1=array[i-1].x,y1=array[i-1].y;
		if(st2[x][y][0][1]==st2[x1][y1][0][1] && st2[x][y][0][0]==st2[x1][y1][0][0] && s[x][y][0][1]==s[x1][y1][0][1] && s[x][y][0][0]==s[x1][y1][0][0])continue;
		long long int tmp=find(x,y);

		if(tmp==1)
			//cout<<s[x][y][0][0]+1<<" "<<st2[x][y][0][0]+1<<" "<<s[x][y][0][1]-1<<" "<<st2[x][y][0][1]-1<<endl;
			//cout<<endl;
		ans+=tmp;
	}
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:55:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
rect.cpp:95:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^

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