Submission #393420

#	Time	Username	Problem	Language	Result	Execution time	Memory
393420		vanic	UFO (IZhO14_ufo)	C++14	100 / 100	922 ms	114732 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;

int n, m, r, k, p;
vector < int > poz;


struct tournament{
	vector < int > t;
	int pot;
	tournament(int sz){
		pot=sz/2;
		while(sz--){
			t.push_back(0);
		}
	}
	void build(){
		for(int x=pot-1; x>0; x--){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	void update(int x, int val){
		t[x]+=val;
		for(x>>=1; x>0; x>>=1){
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	int query1(int L, int D, int x, int val, int puc){
		if(x>=pot){
			poz.push_back(x-pot);
			return puc-1;
		}
		if(t[x*2]>=val){
			puc=query1(L, (L+D)/2, x*2, val, puc);
			if(!puc){
				return 0;
			}
		}
		if(t[x*2+1]>=val){
			puc=query1((L+D)/2+1, D, x*2+1, val, puc);
		}
		return puc;
	}
	int query2(int L, int D, int x, int val, int puc){
		if(x>=pot){
			poz.push_back(x-pot);
			return puc-1;
		}
		if(t[x*2+1]>=val){
			puc=query2((L+D)/2+1, D, x*2+1, val, puc);
			if(!puc){
				return 0;
			}
		}
		if(t[x*2]>=val){
			puc=query2(L, (L+D)/2, x*2, val, puc);
		}
		return puc;
	}
};


vector < tournament > R, S;
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;
	while(pot1<n){
		pot1*=2;
	}
	tournament T1(pot1*2);
	for(int i=0; i<m; i++){
		S.push_back(T1);
	}
	int pot2=1;
	while(pot2<m){
		pot2*=2;
	}
	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].t[j+pot2]=a;
			S[j].t[i+pot1]=a;
			vi.push_back(a);
		}
		pref.push_back(vi1);
		l.push_back(vi);
		vi.clear();
	}
	for(int i=0; i<n; i++){
		R[i].build();
	}
	for(int i=0; i<m; i++){
		S[i].build();
	}
	pref.push_back(vi1);
	char c;
	int b;
	for(int i=0; i<k; i++){
		do{
			c=getchar();
		}while(c<'A' || c>'Z');
		scan(a);
		scan(b);
		a--;
		if(c=='W'){
			R[a].query1(0, pot2-1, 1, b, r);
			for(int j=0; j<(int)poz.size(); j++){
				R[a].update(poz[j]+pot2, -1);
				S[poz[j]].update(a+pot1, -1);
				l[a][poz[j]]--;
			}
		}
		else if(c=='N'){
			S[a].query1(0, pot1-1, 1, b, r);
			for(int j=0; j<(int)poz.size(); j++){
				R[poz[j]].update(a+pot2, -1);
				S[a].update(poz[j]+pot1, -1);
				l[poz[j]][a]--;
			}
		}
		else if(c=='E'){
			R[a].query2(0, pot2-1, 1, b, r);
			for(int j=0; j<(int)poz.size(); j++){
				R[a].update(poz[j]+pot2, -1);
				S[poz[j]].update(a+pot1, -1);
				l[a][poz[j]]--;
			}
		}
		else{
			S[a].query2(0, pot1-1, 1, b, r);
			for(int j=0; j<(int)poz.size(); j++){
				R[poz[j]].update(a+pot2, -1);
				S[a].update(poz[j]+pot1, -1);
				l[poz[j]][a]--;
			}
		}
		poz.clear();
//		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: 100 / 100