Submission #392936

#	Time	Username	Problem	Language	Result	Execution time	Memory
392936		vanic	UFO (IZhO14_ufo)	C++14	25 / 100	2094 ms	114896 KiB

ufo

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <array>

using namespace std;

const int maxn=1e6+5;

typedef long long ll;

struct tournament{
	vector < int > t;
	int pot;
	tournament(int sz){
		for(int i=0; i<sz; i++){
			t.push_back(0);
		}
		pot=sz/2;
	}
	void update(int x, int val){
		t[x]+=val;
		for(x/=2; x>0; x/=2){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d, int val, bool p){
		if(L>=l && D<=d){
//			cout << L << ' ' << D << ' ' << t[x] << endl;
			if(t[x]>=val){
				while(x<pot){
					if(p){
						if(t[x*2]>=val){
							x*=2;
						}
						else{
							x=x*2+1;
						}
					}
					else{
						if(t[x*2+1]>=val){
							x=x*2+1;
						}
						else{
							x*=2;
						}
					}
				}
				return x-pot;
			}
			return -1;
		}
		int vrij=-1;
		if(p){
			if((L+D)/2>=l){
				vrij=query(L, (L+D)/2, x*2, l, d, val, p);
			}
			if(vrij!=-1){
				return vrij;
			}
			if((L+D)/2+1<=d){
				vrij=query((L+D)/2+1, D, x*2+1, l, d, val, p);
			}
		}
		else{
			if((L+D)/2+1<=d){
				vrij=query((L+D)/2+1, D, x*2+1, l, d, val, p);
			}
			if(vrij!=-1){
				return vrij;
			}
			if((L+D)/2>=l){
				vrij=query(L, (L+D)/2, x*2, l, d, val, p);
			}
		}
		return vrij;
	}
};


vector < tournament > R, S;
int n, m, r, k, p;
vector < vector < int > > l;
vector < vector < ll > > pref;
vector < int > vi;
vector < ll > vi1;

void scan(int &a){
	a=0;
	char c=getchar();
	while(c<'0' || c>'9'){
		c=getchar();
	}
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
}


int main(){
	scan(n);
	scan(m);
	scan(r);
	scan(k);
	scan(p);
	int a;
	int pot1=(1<<(int)ceil(log2(n)));
	tournament T1(pot1*2);
	for(int i=0; i<m; i++){
		S.push_back(T1);
	}
	int pot2=(1<<(int)ceil(log2(m)));
	tournament T2(pot2*2);
	for(int i=0; i<n; i++){
		R.push_back(T2);
	}
	vi1.resize(m+1, 0);
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			scan(a);
			R[i].update(j+pot2, a);
			S[j].update(i+pot1, a);
			vi.push_back(a);
		}
		pref.push_back(vi1);
		l.push_back(vi);
		vi.clear();
	}
	pref.push_back(vi1);
	char c;
	int b;
	int pos;
	for(int i=0; i<k; i++){
		do{
			c=getchar();
		}while(c<'A' || c>'Z');
		scan(a);
		scan(b);
		a--;
		if(c=='W'){
			pos=0;
			for(int j=0; j<r; j++){
				pos=R[a].query(0, pot2-1, 1, pos, pot2-1, b, 1);
//				cout << "vracam " << pos << endl;
				if(pos==-1){
					break;
				}
				R[a].update(pos+pot2, -1);
				S[pos].update(a+pot1, -1);
				l[a][pos]--;
				pos++;
			}
		}
		else if(c=='N'){
			pos=0;
			for(int j=0; j<r; j++){
				pos=S[a].query(0, pot1-1, 1, pos, pot1-1, b, 1);
				if(pos==-1){
					break;
				}
				R[pos].update(a+pot2, -1);
				S[a].update(pos+pot1, -1);
				l[pos][a]--;
				pos++;
			}
		}
		else if(c=='E'){
			pos=pot2-1;
			for(int j=0; j<r; j++){
				pos=R[a].query(0, pot2-1, 1, 0, pos, b, 0);
				if(pos==-1){
					break;
				}
				R[a].update(pos+pot2, -1);
				S[pos].update(a+pot1, -1);
				l[a][pos]--;
				pos--;
			}
		}
		else{
			pos=pot1-1;
			for(int j=0; j<r; j++){
				pos=S[a].query(0, pot1-1, 1, 0, pos, b, 0);
				if(pos==-1){
					break;
				}
				R[pos].update(a+pot2, -1);
				S[a].update(pos+pot1, -1);
				l[pos][a]--;
				pos--;
			}
		}
//		printf("dalje\n");
	}
//	printf("kraj\n");
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			pref[i+1][j+1]=pref[i][j+1]+pref[i+1][j]-pref[i][j]+l[i][j];
		}
	}
	ll maksi=0;
	for(int i=p; i<=n; i++){
		for(int j=p; j<=m; j++){
			maksi=max(maksi, pref[i][j]-pref[i-p][j]-pref[i][j-p]+pref[i-p][j-p]);
		}
	}
	printf("%lld\n", maksi);
	return 0;
}

• Subtask 1: 25 / 100