oj.uz

Submission #392896

# Submission time Handle Problem Language Result Execution time Memory
392896 2021-04-22T08:52:14 Z vanic UFO (IZhO14_ufo) C++14
5 / 100
 2000 ms 117092 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;

int main(){
	scanf("%d%d%d%d%d", &n, &m, &r, &k, &p);
	vector < int > vi;
	vector < ll > vi1;
	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;
//	printf("krecem\n");
	for(int i=0; i<k; i++){
		getchar();
		scanf("%c%d%d", &c, &a, &b);
//		printf("%c %d %d\n", 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]);
		}
	}
	printf("%lld\n", maksi);
	return 0;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d%d%d%d%d", &n, &m, &r, &k, &p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   scanf("%c%d%d", &c, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Execution timed out 2070 ms 204 KB Time limit exceeded
3 Runtime error 2 ms 588 KB Execution killed with signal 11
4 Execution timed out 2098 ms 716 KB Time limit exceeded
5 Execution timed out 2087 ms 2888 KB Time limit exceeded
6 Correct 287 ms 20724 KB Output is correct
7 Runtime error 434 ms 93100 KB Execution killed with signal 11
8 Runtime error 304 ms 89404 KB Execution killed with signal 11
9 Runtime error 299 ms 80872 KB Execution killed with signal 11
10 Runtime error 313 ms 89428 KB Execution killed with signal 11
11 Execution timed out 2078 ms 38828 KB Time limit exceeded
12 Runtime error 298 ms 89324 KB Execution killed with signal 11
13 Runtime error 327 ms 98672 KB Execution killed with signal 11
14 Execution timed out 2075 ms 38948 KB Time limit exceeded
15 Execution timed out 2074 ms 46184 KB Time limit exceeded
16 Execution timed out 2066 ms 38980 KB Time limit exceeded
17 Execution timed out 2098 ms 53416 KB Time limit exceeded
18 Runtime error 285 ms 87848 KB Execution killed with signal 11
19 Runtime error 315 ms 106184 KB Execution killed with signal 11
20 Execution timed out 2094 ms 117092 KB Time limit exceeded