oj.uz

Submission #393419

# Submission time Handle Problem Language Result Execution time Memory
393419 2021-04-23T11:58:05 Z vanic UFO (IZhO14_ufo) C++14
0 / 100
 329 ms 232660 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;

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;
		}
		puc=query1(L, (L+D)/2, x*2, val, puc);
		if(!puc){
			return 0;
		}
		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;
		}
		puc=query2((L+D)/2+1, D, x*2+1, val, puc);
		if(!puc){
			return 0;
		}
		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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Runtime error 1 ms 332 KB Execution killed with signal 11
3 Runtime error 1 ms 476 KB Execution killed with signal 11
4 Runtime error 1 ms 972 KB Execution killed with signal 11
5 Runtime error 6 ms 4996 KB Execution killed with signal 11
6 Runtime error 44 ms 35000 KB Execution killed with signal 11
7 Runtime error 129 ms 87176 KB Execution killed with signal 11
8 Runtime error 98 ms 87308 KB Execution killed with signal 11
9 Runtime error 84 ms 78756 KB Execution killed with signal 11
10 Runtime error 94 ms 87192 KB Execution killed with signal 11
11 Runtime error 80 ms 74412 KB Execution killed with signal 11
12 Runtime error 92 ms 87124 KB Execution killed with signal 11
13 Runtime error 105 ms 96276 KB Execution killed with signal 11
14 Runtime error 83 ms 74352 KB Execution killed with signal 11
15 Runtime error 99 ms 87188 KB Execution killed with signal 11
16 Runtime error 81 ms 74344 KB Execution killed with signal 11
17 Runtime error 122 ms 96304 KB Execution killed with signal 11
18 Runtime error 96 ms 85544 KB Execution killed with signal 11
19 Runtime error 110 ms 103988 KB Execution killed with signal 11
20 Runtime error 329 ms 232660 KB Execution killed with signal 11