Submission #341147

#	Time	Username	Problem	Language	Result	Execution time	Memory
341147		juggernaut	UFO (IZhO14_ufo)	C++14	100 / 100	1561 ms	133484 KiB

ufo

#include<bits/stdc++.h>
using namespace std;
int remain;
vector<int>vec;
struct data{
	vector<int>t;
	void reset(int n){t.resize(n<<2);}
	void update(int v,int tl,int tr,int pos, int val){
		if(tl==tr){
			t[v]=val;
			return;
		}
		int mid=(tl+tr)>>1;
		if(pos<=mid)update(v<<1,tl,mid,pos,val);
		else update(v<<1|1,mid+1,tr,pos,val);
		t[v]=max(t[v<<1],t[v<<1|1]);
	}
	void findfirst(int v,int tl,int tr,int x){
		if(remain==0||t[v]<x)return;
		if(tl==tr){
			remain--;
			vec.push_back(tl);
			return;
		}
		int mid=(tl+tr)>>1;
		findfirst(v<<1,tl,mid,x);
		findfirst(v<<1|1,mid+1,tr,x);
	}
	void findlast(int v,int tl,int tr,int x){
		if(remain==0||t[v]<x)return;
		if(tl==tr){
			remain--;
			vec.push_back(tl);
			return;
		}
		int mid=(tl+tr)>>1;
		findlast(v<<1|1,mid+1,tr,x);
		findlast(v<<1,tl,mid,x);
	}
};
data row[1000005],col[1000005];
int main(){
	int n,m,r,k,p;
	scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
	int a[n+5][m+5];
	memset(a,0,sizeof(a));
	for(int i=1;i<=m;i++)col[i].reset(n+1);
	for(int i=1;i<=n;i++){
		row[i].reset(m+1);
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			row[i].update(1,1,m,j,a[i][j]);
			col[j].update(1,1,n,i,a[i][j]);
		}
	}
	char ch;
	int id,h;
	while(k--){
		vec.clear();
		remain=r;
		cin>>ch;
		scanf("%d%d", &id, &h);
		if(ch=='W'){
			row[id].findfirst(1,1,m,h);
			for(auto to:vec){
				a[id][to]--;
				row[id].update(1,1,m,to,a[id][to]);
				col[to].update(1,1,n,id,a[id][to]);
			}
		}
		if(ch=='N'){
			col[id].findfirst(1,1,n,h);
			for(auto to:vec){
				a[to][id]--;
				row[to].update(1,1,m,id,a[to][id]);
				col[id].update(1,1,n,to,a[to][id]);
			}
		}
		if(ch=='E'){
			row[id].findlast(1,1,m,h);
			for(auto to:vec){
				a[id][to]--;
				row[id].update(1,1,m,to,a[id][to]);
				col[to].update(1,1,n,id,a[id][to]);
			}
		}
		if(ch=='S'){
			col[id].findlast(1,1,n,h);
			for(auto to:vec){
				a[to][id]--;
				row[to].update(1,1,m,id,a[to][id]);
				col[id].update(1,1,n,to,a[to][id]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=0,y=0;
			if(j>=2)y=a[i][j-1];
			if(i>=2)x=a[i-1][j];
			a[i][j]=a[i][j]+x+y-a[i-1][j-1];
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(i>=p&&j>=p)
				ans=max(ans,a[i][j]-a[i][j-p]-a[i-p][j]+a[i-p][j-p]);
	cout<<ans;
}

Compilation message (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d%d%d%d%d",&n,&m,&r,&k,&p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |    scanf("%d",&a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~
ufo.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d%d", &id, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100