Submission #40632

#	Time	Username	Problem	Language	Result	Execution time	Memory
40632		faustaadp	UFO (IZhO14_ufo)	C++11	100 / 100	1994 ms	102448 KiB

ufo

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
int n,m,r,k,p,i,j,ta,tb,hv,L,R,C,hs;
char ct;
vector<vector<int> > a,str,stc,pr; 
pair<int,int> hz;
void ini()
{
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=m;j++)
			vt.pb(0);
		a.pb(vt);
	}
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=m;j++)
			vt.pb(0);
		pr.pb(vt);
	}
	for(i=0;i<=n;i++)
	{
		vector<int> vt;
		for(j=0;j<=4*m;j++)
			vt.pb(0);
		stc.pb(vt);
	}
	for(i=0;i<=m;i++)
	{
		vector<int> vt;
		for(j=0;j<=4*n;j++)
			vt.pb(0);
		str.pb(vt);
	}
}
void upr(int aa,int bb,int cc,int dd,int ee,int ff)
{
	if(aa==bb)
		str[ff][ee]=dd;
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upr(aa,ce,cc,dd,ee*2,ff);
		else
			upr(ce+1,bb,cc,dd,ee*2+1,ff);
		str[ff][ee]=max(str[ff][ee*2],str[ff][ee*2+1]);
	}		
}
void upc(int aa,int bb,int cc,int dd,int ee,int ff)
{
	if(aa==bb)
		stc[ff][ee]=dd;
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			upc(aa,ce,cc,dd,ee*2,ff);
		else
			upc(ce+1,bb,cc,dd,ee*2+1,ff);
		stc[ff][ee]=max(stc[ff][ee*2],stc[ff][ee*2+1]);
	}		
}
pair<int,int> nilN(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,str[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(str[ff][ee*2]>=tb)
		return nilN(aa,ce,ee*2,ff);
	else
		return nilN(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilS(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,str[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(str[ff][ee*2+1]>=tb)
		return nilS(ce+1,bb,ee*2+1,ff);
	else
		return nilS(aa,ce,ee*2,ff);
}
pair<int,int> nilW(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,stc[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(stc[ff][ee*2]>=tb)
		return nilW(aa,ce,ee*2,ff);
	else
		return nilW(ce+1,bb,ee*2+1,ff);
}
pair<int,int> nilE(int aa,int bb,int ee,int ff)
{
	if(aa==bb)
		return mp(aa,stc[ff][ee]-1);
	int ce=(aa+bb)/2;
	if(stc[ff][ee*2+1]>=tb)
		return nilE(ce+1,bb,ee*2+1,ff);
	else
		return nilE(aa,ce,ee*2,ff);
}
int nil(int aa,int bb,int cc,int ee,int ff)
{
	if(aa==bb)
		return stc[ff][ee];
	else
	{
		int ce=(aa+bb)/2;
		if(cc<=ce)
			return nil(aa,ce,cc,ee*2,ff);
		else
			return nil(ce+1,bb,cc,ee*2+1,ff);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>r>>k>>p;
	ini();
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			cin>>ta;
			upr(1,n,i,ta,1,j);
			upc(1,m,j,ta,1,i);
		}
	while(k--)
	{
		cin>>ct>>ta>>tb;
		vector<pair<int,int> > v;
		if(ct=='N')
		{
			for(i=1;i<=r;i++)
			{
				if(str[ta][1]<tb)
					break;
				hz=nilN(1,n,1,ta);
				upr(1,n,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,v[i].fi,v[i].se,1,ta);
				upc(1,m,ta,v[i].se,1,v[i].fi);
			}
		}
		else
		if(ct=='S')
		{
			for(i=1;i<=r;i++)
			{
				if(str[ta][1]<tb)
					break;
				hz=nilS(1,n,1,ta);
				upr(1,n,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,v[i].fi,v[i].se,1,ta);
				upc(1,m,ta,v[i].se,1,v[i].fi);
			}
		}
		else
		if(ct=='W')
		{
			for(i=1;i<=r;i++)
			{
				if(stc[ta][1]<tb)
					break;
				hz=nilW(1,m,1,ta);
				upc(1,m,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,ta,v[i].se,1,v[i].fi);
				upc(1,m,v[i].fi,v[i].se,1,ta);
			}
		}
		else
		{
			for(i=1;i<=r;i++)
			{
				if(stc[ta][1]<tb)
					break;
				hz=nilE(1,m,1,ta);
				upc(1,m,hz.fi,-10e8,1,ta);
				v.pb(hz);
			}
			for(i=0;i<v.size();i++)
			{
				upr(1,n,ta,v[i].se,1,v[i].fi);
				upc(1,m,v[i].fi,v[i].se,1,ta);
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a[i][j]=nil(1,m,j,1,i);
			pr[i][j]=pr[i][j-1]+pr[i-1][j]-pr[i-1][j-1]+a[i][j];
	//		cout<<a[i][j]<<" ";
		}
	//	cout<<"\n";
	}
	for(i=1;i+p-1<=n;i++)
		for(j=1;j+p-1<=m;j++)
			hs=max(hs,pr[i+p-1][j+p-1]-pr[i-1][j+p-1]-pr[i+p-1][j-1]+pr[i-1][j-1]);
	cout<<hs<<"\n";
}

Compilation message (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:150:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:167:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:184:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^
ufo.cpp:200:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(i=0;i<v.size();i++)
             ^

• Subtask 1: 100 / 100