Submission #1140749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140749		Faisal_Saqib	Toy (CEOI24_toy)	C++17	100 / 100	660 ms	98152 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

const int N=3000;
char grid[N][N];
int pre_row[N][N],pre_col[N][N],U_max[N][N],U_min[N][N],L_max[N][N],L_min[N][N];
bool seen[N][N];
int k,l,h,w;
int get_row(int x,int y)
{
	return pre_row[x][y+k]-pre_row[x][y];
}
int get_col(int x,int y)
{
	return pre_col[x+l][y]-pre_col[x][y];
}
queue<pair<int,int>> q;
bool intersection(int x1,int y1,int x2,int y2)
{
	return max(x1,x2)<=min(y1,y2);
}
int main()
{
	ios::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin>>w>>h>>k>>l;
	int xh1,yh1,xv1,yv1;
	cin>>xh1>>yh1>>xv1>>yv1;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin>>grid[i][j];
			pre_row[i][j+1]=pre_row[i][j]+(grid[i][j]=='X');
			pre_col[i+1][j]=pre_col[i][j]+(grid[i][j]=='X');
		}
	}
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			U_max[i][j]=L_max[i][j]=-1e9;
			U_min[i][j]=L_min[i][j]=1e9;
		}
	}
	// O(N^4) --> O(N^3) done
	for(int i=0;i<h;i++)
	{
		set<int> vals;
		for(int j=0;j<w-k+1;j++)
		{
			if((pre_row[i][j+k]-pre_row[i][j])==0)
			{
				vals.insert(j);
			}
		}
				// j-min(j,k-1) to j-max(0,k+j-w)
		for(int j=0;j<w;j++)
		{
			int las=j-min(j,k-1),ras=j-max(0,k+j-w);
			auto it=vals.lower_bound(las);
			if(it!=end(vals) and (*it)<=ras)
			{
				// j-L = *it
				// j - *it = l
				L_min[i][j]=min(L_min[i][j], j - (*it));
				L_max[i][j]=max(L_max[i][j], j - (*it));
			}
			it=vals.upper_bound(ras);
			if(begin(vals)!=it)
			{
				it--;
				if(las<=(*it))
				{
					L_min[i][j]=min(L_min[i][j], j - (*it));
					L_max[i][j]=max(L_max[i][j], j - (*it));					
				}
			}
		}
	}
	for(int j=0;j<w;j++)
	{
		set<int> vals;
		for(int i=0;i<h-l+1;i++)
		{
			if((pre_col[i+l][j]-pre_col[i][j])==0)
			{
				vals.insert(i);
			}
		}
		for(int i=0;i<h;i++)
		{
			int las=i-min(i,l-1),ras=i-max(0,l+i-h);
			auto it=vals.lower_bound(las);
			if(it!=end(vals) and (*it)<=ras)
			{
				// j-L = *it
				// j - *it = l
				U_min[i][j]=min(U_min[i][j], i - (*it));
				U_max[i][j]=max(U_max[i][j], i - (*it));
			}
			it=vals.upper_bound(ras);
			if(begin(vals)!=it)
			{
				it--;
				if(las<=(*it))
				{
					U_min[i][j]=min(U_min[i][j], i - (*it));
					U_max[i][j]=max(U_max[i][j], i - (*it));					
				}
			}
			// cout<<"Value of U "<<i<<' '<<j<<' '<<U_max[i][j]<<' '<<U_min[i][j]<<endl;
		}
	}
	/*
	i in range(n)
		j in range(m)
			L in range(j+k-w,j)

				find the range of j-L
				// j-j =0
				// [0,w-k] 
				// we want maximum x in the range [0,w-k] such pre[i][x+k]-pre[i][x] == 0
				// mx is x min is y
				// then L_min[i][j] = j-x
				// then L_max[i][j] = j-y
	*/
	vector<pair<int,int>> dir={{-1,0},{0,-1},{0,1},{1,0}};
	q.push({yh1,xv1});
	seen[yh1][xv1]=1;
	int tp=0,x,y,y1,x1;
	while(q.size()>0)
	{
		auto it=q.front();
		q.pop();
		if(grid[it.ff][it.ss]=='*')
		{
			cout<<"YES"<<endl;
			return 0;
		}
		x=it.ff,y=it.ss;
		for(auto&[dx,dy]:dir)
		{
			it.ff+=dx;
			it.ss+=dy;
			x1=it.ff;
			y1=it.ss;
			if(min(x1,y1)>=0 and x1<h and y1<w and !seen[x1][y1])
			{
				if(intersection(x-U_max[x][y],x-U_min[x][y],x1-U_max[x1][y1],x1-U_min[x1][y1]) and intersection(y-L_max[x][y],y-L_min[x][y],y1-L_max[x1][y1],y1-L_min[x1][y1]))
				{
					q.push({x1,y1});
					seen[x1][y1]=1;
				}
			}
			it.ff-=dx;
			it.ss-=dy;
		}
	}
	cout<<"NO"<<endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27