oj.uz

Submission #392933

# Submission time Handle Problem Language Result Execution time Memory
392933 2021-04-22T10:21:58 Z vanic UFO (IZhO14_ufo) C++14
5 / 100
 2000 ms 232964 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'){
		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++){
		c=getchar();
		getchar();
		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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 288 KB Execution killed with signal 11
2 Execution timed out 2072 ms 284 KB Time limit exceeded
3 Runtime error 1 ms 460 KB Execution killed with signal 11
4 Execution timed out 2071 ms 716 KB Time limit exceeded
5 Execution timed out 2076 ms 2760 KB Time limit exceeded
6 Correct 156 ms 17732 KB Output is correct
7 Execution timed out 2093 ms 43304 KB Time limit exceeded
8 Execution timed out 2083 ms 43252 KB Time limit exceeded
9 Runtime error 158 ms 78968 KB Execution killed with signal 11
10 Execution timed out 2084 ms 43244 KB Time limit exceeded
11 Execution timed out 2078 ms 36972 KB Time limit exceeded
12 Execution timed out 2067 ms 43364 KB Time limit exceeded
13 Runtime error 181 ms 96480 KB Execution killed with signal 11
14 Execution timed out 2074 ms 36928 KB Time limit exceeded
15 Execution timed out 2083 ms 43200 KB Time limit exceeded
16 Execution timed out 2077 ms 36964 KB Time limit exceeded
17 Execution timed out 2085 ms 47792 KB Time limit exceeded
18 Runtime error 157 ms 85804 KB Execution killed with signal 11
19 Execution timed out 2091 ms 51504 KB Time limit exceeded
20 Runtime error 327 ms 232964 KB Execution killed with signal 11