oj.uz

Submission #392936

# Submission time Handle Problem Language Result Execution time Memory
392936 2021-04-22T10:24:30 Z vanic UFO (IZhO14_ufo) C++14
25 / 100
 2000 ms 114896 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Execution timed out 2083 ms 204 KB Time limit exceeded
3 Execution timed out 2086 ms 332 KB Time limit exceeded
4 Execution timed out 2081 ms 588 KB Time limit exceeded
5 Execution timed out 2091 ms 2504 KB Time limit exceeded
6 Correct 151 ms 17348 KB Output is correct
7 Execution timed out 2092 ms 43076 KB Time limit exceeded
8 Correct 146 ms 43320 KB Output is correct
9 Execution timed out 2082 ms 38940 KB Time limit exceeded
10 Execution timed out 2075 ms 43012 KB Time limit exceeded
11 Execution timed out 2087 ms 36772 KB Time limit exceeded
12 Execution timed out 2061 ms 43036 KB Time limit exceeded
13 Execution timed out 2094 ms 47536 KB Time limit exceeded
14 Execution timed out 2088 ms 36776 KB Time limit exceeded
15 Execution timed out 2076 ms 43056 KB Time limit exceeded
16 Execution timed out 2085 ms 36776 KB Time limit exceeded
17 Execution timed out 2087 ms 47536 KB Time limit exceeded
18 Execution timed out 2090 ms 42284 KB Time limit exceeded
19 Correct 271 ms 51428 KB Output is correct
20 Correct 1479 ms 114896 KB Output is correct