Submission #1186150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186150		PieArmy	UFO (IZhO14_ufo)	C++20	100 / 100	624 ms	195988 KiB

ufo

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
#define mid ((left+right)>>1)
using namespace std;

struct Seg{
	int n;
	vector<ll>tree,arr;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=arr[left];
			return;
		}
		build(node*2,left,mid);
		build(node*2+1,mid+1,right);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void init(vector<ll>Arr){
		arr=Arr;
		n=arr.size();
		tree.resize(n<<2,0);
		build();
	}
	int x;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]--;
			return;
		}
		if(x>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int tar){
		x=tar;
		up();
	}
	int walk1(int val,int loc,int node=1,int left=0,int right=-1){
		if(tree[node]<val)return n;
		if(right==-1)right=n-1;
		if(right<loc)return n;
		if(left==right)return left;
		int res=walk1(val,loc,node*2,left,mid);
		if(res==n)return walk1(val,loc,node*2+1,mid+1,right);
		return res;
	}
	int walk2(int val,int loc,int node=1,int left=0,int right=-1){
		if(tree[node]<val)return -1;
		if(right==-1)right=n-1;
		if(left>loc)return -1;
		if(left==right)return left;
		int res=walk2(val,loc,node*2+1,mid+1,right);
		if(res==-1)return walk2(val,loc,node*2,left,mid);
		return res;
	}
	void dfs(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			arr[left]=tree[node];
			return;
		}
		dfs(node*2,left,mid);
		dfs(node*2+1,mid+1,right);
	}
	vector<ll> getvals(){
		dfs();
		return arr;
	}
};

int n,m,r,k,p;
vector<vector<ll>>mat;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m>>r>>k>>p;
	mat.resize(n,vector<ll>(m));
	Seg row[n],col[m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>mat[i][j];
		}
		row[i].init(mat[i]);
	}
	for(int i=0;i<m;i++){
		vector<ll>v;
		for(int j=0;j<n;j++){
			v.pb(mat[j][i]);
		}
		col[i].init(v);
	}
	for(int i=0;i<k;i++){
		char c;cin>>c;
		int x,h;cin>>x>>h;
		x--;
		if(c=='N'){
			int s=r;
			int pos=0;
			while(s&&pos!=n){
				pos=col[x].walk1(h,pos);
				if(pos==n)break;
				col[x].update(pos);
				row[pos].update(x);
				pos++;
				s--;
			}
		}
		if(c=='S'){
			int s=r;
			int pos=n-1;
			while(s&&pos!=-1){
				pos=col[x].walk2(h,pos);
				if(pos==-1)break;
				col[x].update(pos);
				row[pos].update(x);
				pos--;
				s--;
			}
		}
		if(c=='W'){
			int s=r;
			int pos=0;
			while(s&&pos!=m){
				pos=row[x].walk1(h,pos);
				if(pos==m)break;
				row[x].update(pos);
				col[pos].update(x);
				pos++;
				s--;
			}
		}
		if(c=='E'){
			int s=r;
			int pos=m-1;
			while(s&&pos!=-1){
				pos=row[x].walk2(h,pos);
				if(pos==-1)break;
				row[x].update(pos);
				col[pos].update(x);
				pos--;
				s--;
			}
		}
	}
	for(int i=0;i<n;i++){
		mat[i]=row[i].getvals();
		if(i)mat[i][0]+=mat[i-1][0];
		for(int j=1;j<m;j++){
			mat[i][j]+=mat[i][j-1];
			if(i){
				mat[i][j]+=mat[i-1][j]-mat[i-1][j-1];
			}
		}
	}
	ll ans=0;
	if(p==0){
		cout<<"0\n";
		return 0;
	}
	for(int i=p-1;i<n;i++){
		for(int j=p-1;j<m;j++){
			ll sum=mat[i][j];
			if(i-p>=0){
				sum-=mat[i-p][j];
			}
			if(j-p>=0){
				sum-=mat[i][j-p];
			}
			if(i-p>=0&&j-p>=0){
				sum+=mat[i-p][j-p];
			}
			ans=max(ans,sum);
		}
	}
	cout<<ans<<endl;
}

• Subtask 1: 100 / 100