oj.uz

Submission #393410

# Submission time Handle Problem Language Result Execution time Memory
393410 2021-04-23T11:26:58 Z vanic UFO (IZhO14_ufo) C++14
25 / 100
 2000 ms 115404 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){
		t.resize(sz, 0);
		pot=sz/2;
	}
	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 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;
	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;
	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 2074 ms 204 KB Time limit exceeded
3 Execution timed out 2076 ms 332 KB Time limit exceeded
4 Execution timed out 2088 ms 716 KB Time limit exceeded
5 Execution timed out 2076 ms 2888 KB Time limit exceeded
6 Correct 112 ms 20684 KB Output is correct
7 Execution timed out 2072 ms 47208 KB Time limit exceeded
8 Correct 85 ms 47032 KB Output is correct
9 Execution timed out 2086 ms 40752 KB Time limit exceeded
10 Execution timed out 2085 ms 44712 KB Time limit exceeded
11 Execution timed out 2036 ms 38300 KB Time limit exceeded
12 Execution timed out 2048 ms 44712 KB Time limit exceeded
13 Execution timed out 2071 ms 49840 KB Time limit exceeded
14 Execution timed out 2087 ms 38440 KB Time limit exceeded
15 Execution timed out 2084 ms 45608 KB Time limit exceeded
16 Execution timed out 2080 ms 38440 KB Time limit exceeded
17 Execution timed out 2070 ms 52140 KB Time limit exceeded
18 Execution timed out 2082 ms 45100 KB Time limit exceeded
19 Correct 210 ms 55380 KB Output is correct
20 Correct 1718 ms 115404 KB Output is correct