oj.uz

Submission #392902

# Submission time Handle Problem Language Result Execution time Memory
392902 2021-04-22T09:06:57 Z vanic UFO (IZhO14_ufo) C++14
25 / 100
 2000 ms 117196 KB 
#include <iostream>
//#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;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> r >> k >> 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++){
			cin >> 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++){
		cin >> c >> a >> 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]);
		}
	}
	cout << maksi << '\n';
	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 2080 ms 204 KB Time limit exceeded
3 Execution timed out 2079 ms 336 KB Time limit exceeded
4 Execution timed out 2054 ms 588 KB Time limit exceeded
5 Execution timed out 2085 ms 2504 KB Time limit exceeded
6 Correct 190 ms 17332 KB Output is correct
7 Execution timed out 2088 ms 43128 KB Time limit exceeded
8 Correct 227 ms 45328 KB Output is correct
9 Execution timed out 2062 ms 38912 KB Time limit exceeded
10 Execution timed out 2055 ms 43024 KB Time limit exceeded
11 Execution timed out 2089 ms 36900 KB Time limit exceeded
12 Execution timed out 2088 ms 43172 KB Time limit exceeded
13 Execution timed out 2088 ms 47552 KB Time limit exceeded
14 Execution timed out 2080 ms 36840 KB Time limit exceeded
15 Execution timed out 2075 ms 43020 KB Time limit exceeded
16 Execution timed out 2086 ms 36812 KB Time limit exceeded
17 Execution timed out 2082 ms 47556 KB Time limit exceeded
18 Execution timed out 2085 ms 43128 KB Time limit exceeded
19 Correct 358 ms 54268 KB Output is correct
20 Correct 1604 ms 117196 KB Output is correct