Submission #1140723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140723		Faisal_Saqib	Toy (CEOI24_toy)	C++17	0 / 100	8 ms	11336 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++)
	{
		vector<int> vals;
		for(int j=0;j<w-k+1;j++)
		{
			if((pre_row[i][j+k]-pre_row[i][j])==0)
			{
				vals.push_back(j);
			}
		}
		for(int j=0;j<w and vals.size()>0;j++)
		{
			// x = j-L
			// x+L = j
			// L = j-x
			L_min[i][j]=min(L_min[i][j],j-vals.back());
			L_max[i][j]=max(L_max[i][j],j-vals[0]);
		}
	}
	for(int j=0;j<w;j++)
	{
		vector<int> vals;
		for(int i=0;i<h-l+1;i++)
		{
			if((pre_col[i+l][j]-pre_col[i][j])==0)
			{
				vals.push_back(i);
			}
		}
		for(int i=0;i<h and vals.size()>0;i++)
		{
			// x = j-L
			// x+L = j
			// L = j-x
			U_min[i][j]=min(U_min[i][j],i-vals.back());
			U_max[i][j]=max(U_max[i][j],i-vals[0]);
		}
	}
	/*
	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: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27