oj.uz

Submission #393418

# Submission time Handle Problem Language Result Execution time Memory
393418 2021-04-23T11:56:54 Z vanic UFO (IZhO14_ufo) C++14
15 / 100
 505 ms 114788 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=query1((L+D)/2+1, D, x*2+1, val, puc);
		if(!puc){
			return 0;
		}
		puc=query1(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
15.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 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 6 ms 620 KB Output isn't correct
5 Runtime error 7 ms 4936 KB Execution killed with signal 11
6 Incorrect 85 ms 17412 KB Output isn't correct
7 Runtime error 107 ms 87188 KB Execution killed with signal 11
8 Runtime error 96 ms 87172 KB Execution killed with signal 11
9 Runtime error 91 ms 78700 KB Execution killed with signal 11
10 Runtime error 93 ms 87144 KB Execution killed with signal 11
11 Incorrect 256 ms 37844 KB Output isn't correct
12 Runtime error 91 ms 87212 KB Execution killed with signal 11
13 Runtime error 113 ms 96256 KB Execution killed with signal 11
14 Correct 238 ms 37840 KB Output is correct
15 Runtime error 98 ms 87136 KB Execution killed with signal 11
16 Correct 333 ms 40024 KB Output is correct
17 Runtime error 120 ms 96304 KB Execution killed with signal 11
18 Runtime error 96 ms 85552 KB Execution killed with signal 11
19 Runtime error 108 ms 103964 KB Execution killed with signal 11
20 Correct 505 ms 114788 KB Output is correct