Submission #393420

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393420	2021-04-23T12:01:02 Z	vanic	UFO (IZhO14_ufo)	C++14	100 / 100	922 ms	114732 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	7 ms	624 KB	Output is correct
5	Correct	48 ms	2824 KB	Output is correct
6	Correct	90 ms	17404 KB	Output is correct
7	Correct	107 ms	45244 KB	Output is correct
8	Correct	76 ms	43064 KB	Output is correct
9	Correct	207 ms	40216 KB	Output is correct
10	Correct	283 ms	44472 KB	Output is correct
11	Correct	165 ms	36772 KB	Output is correct
12	Correct	284 ms	44468 KB	Output is correct
13	Correct	359 ms	49672 KB	Output is correct
14	Correct	331 ms	36716 KB	Output is correct
15	Correct	414 ms	44976 KB	Output is correct
16	Correct	83 ms	36780 KB	Output is correct
17	Correct	645 ms	50868 KB	Output is correct
18	Correct	91 ms	44844 KB	Output is correct
19	Correct	160 ms	51556 KB	Output is correct
20	Correct	922 ms	114732 KB	Output is correct