Submission #5691

#	Time	Username	Problem	Language	Result	Execution time	Memory
5691		cki86201	UFO (IZhO14_ufo)	C++98	100 / 100	1719 ms	76260 KiB

ufo

#include<stdio.h>
#include<vector>
using namespace std;

vector<vector <int> > inp;
int N, M, R, K, P;

struct node{
	node(){v=x=0,link[0]=link[1]=0;}
	int v, x;
	node *link[2];
	inline void pushup(){
		x = max(v, max(link[0] ? link[0]->x : 0, link[1] ? link[1]->x : 0));
	}
	void build(int xy,int cl,int s,int d){
		int m = (s+d) >> 1;
		v = (xy ? inp[m][cl] : inp[cl][m]);
		if(s<m){
			link[0] = new node();
			link[0]->build(xy, cl, s, m-1);
		}
		if(m<d){
			link[1] = new node();
			link[1]->build(xy, cl, m+1, d);
		}
		pushup();
	}
	void update(int w,int s,int d){
		int m = (s+d)>>1;
		if(w == m)--v;
		else if(w<m)link[0]->update(w, s, m-1);
		else link[1]->update(w, m+1, d);
		pushup();
	}
	int get_min(int h,int s,int d,int L){
		if(x < h)return -1;
		int m = (s+d)>>1;
		if(link[0] && L < m-1){
			int t = link[0]->get_min(h, s, m-1, L);
			if(t != -1)return t;
		}
		if(L < m && v >= h)return m;
		if(link[1]){
			int t = link[1]->get_min(h, m+1, d, L);
			if(t != -1)return t;
		}
		return -1;
	}
	int get_max(int h,int s,int d,int L){
		if(x < h)return -1;
		int m = (s+d)>>1;
		if(link[1] && L > m+1){
			int t = link[1]->get_max(h, m+1, d, L);
			if(t != -1)return t;
		}
		if(L > m && v >= h)return m;
		if(link[0]){
			int t = link[0]->get_max(h, s, m-1, L);
			if(t != -1)return t;
		}
		return -1;
	}
};

vector <node*> xr, yr;

void update(int x,int y)
{
	inp[x][y]--;
	xr[x]->update(y, 0, M-1);
	yr[y]->update(x, 0, N-1);
}

int main()
{
	scanf("%d%d%d%d%d",&N,&M,&R,&K,&P);
	int i, j;
	inp.resize(N);
	for(i=0;i<N;i++){
		inp[i].resize(M);
		for(j=0;j<M;j++)scanf("%d",&inp[i][j]);
	}
	xr.resize(N), yr.resize(M);
	for(i=0;i<N;i++)xr[i] = new node(), xr[i]->build(0, i, 0, M-1);
	for(i=0;i<M;i++)yr[i] = new node(), yr[i]->build(1, i, 0, N-1);
	for(int tt=0;tt<K;tt++){
		char c[2];
		int w, h;
		scanf("%s%d%d",c,&w,&h);
		--w;
		if(c[0] == 'N'){
			int t = -1;
			for(i=0;i<R;i++){
				t = yr[w]->get_min(h, 0, N-1, t);
				if(t == -1)break;
				update(t, w);
			}
		}
		else if(c[0] == 'S'){
			int t = N;
			for(i=0;i<R;i++){
				t = yr[w]->get_max(h, 0, N-1, t);
				if(t == -1)break;
				update(t, w);
			}
		}
		else if(c[0] == 'W'){
			int t = -1;
			for(i=0;i<R;i++){
				t = xr[w]->get_min(h, 0, M-1, t);
				if(t == -1)break;
				update(w, t);
			}
		}
		else{
			int t = M;
			for(i=0;i<R;i++){
				t = xr[w]->get_max(h, 0, M-1, t);
				if(t == -1)break;
				update(w, t);
			}
		}
	}
	for(i=0;i<N;i++){
		int sum = 0;
		for(j=0;j<P;j++)sum += inp[i][j];
		int save = inp[i][0];
		inp[i][0] = sum;
		for(j=0;j<M-P;j++){
			sum += inp[i][j+P] - save;
			save = inp[i][j+1];
			inp[i][j+1] = sum;
		}
	}
	for(j=0;j<M-P+1;j++){
		int sum = 0;
		for(i=0;i<P;i++)sum += inp[i][j];
		int save = inp[0][j];
		inp[0][j] = sum;
		for(i=0;i<N-P;i++){
			sum += inp[i+P][j] - save;
			save = inp[i+1][j];
			inp[i+1][j] = sum;
		}
	}
	int ans = 0;
	for(i=0;i<N-P+1;i++)for(j=0;j<M-P+1;j++)ans = max(ans, inp[i][j]);
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:76:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d",&N,&M,&R,&K,&P);
                                    ^
ufo.cpp:81:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(j=0;j<M;j++)scanf("%d",&inp[i][j]);
                                         ^
ufo.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d",c,&w,&h);
                          ^

• Subtask 1: 100 / 100