Submission #393436

#	Time	Username	Problem	Language	Result	Execution time	Memory
393436		patrikpavic2	UFO (IZhO14_ufo)	C++17	25 / 100	2105 ms	231640 KiB

ufo

#include <cstdio>
#include <cstring>
#include <vector>

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 1e6 + 500;

struct tournament{
	vi T;
	int off;
	void build(vector < int > &v){
		for(off = 1; (int)v.size() > off; off <<= 1);
		T.resize(2 * off);
		for(int i = 0;i < (int)v.size();i++) 
			T[off + i] = v[i];
		for(int i = off - 1; i ; i--)
			T[i] = max(T[2 * i], T[2 * i + 1]);
	}
	void update(int i){
		T[off + i]--;
		for(i = (i + off) / 2 ; i ; i--)
			T[i] = max(T[2 * i], T[2 * i + 1]);
	}
	vi ans;
	void nadi(int i, int x, int kol, bool L){
		if(i >= off) {
			ans.PB(i - off);
			return;
		}
		if(T[2 * i] >= x && (int)ans.size() < kol && L)
			nadi(2 * i, x, kol, L);
		if(T[2 * i + 1] >= x && (int)ans.size() < kol)
			nadi(2 * i + 1, x, kol, L);
		if(T[2 * i] >= x && (int)ans.size() < kol && !L)
			nadi(2 * i, x, kol, L);
	}
};

vi vR[N], vC[N];
tournament R[N], C[N];
int n, m, r, q, p;

int main(){
	scanf("%d%d%d%d%d", &n, &m, &r, &q, &p);
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			int x; scanf("%d", &x);
			vR[i].PB(x); vC[j].PB(x);
		}
	}
	for(int i = 0;i < n;i++)
		R[i].build(vR[i]);
	for(int j = 0;j < m;j++)
		C[j].build(vC[j]);
	for(int i = 0;i < q;i++){
		char c; int pos, h; scanf(" %c%d%d", &c, &pos, &h);
		pos--;
		if(c == 'N' || c == 'S'){
			C[pos].nadi(1, h, r, c == 'N');
			for(int x : C[pos].ans)
				C[pos].update(x), R[x].update(pos);
			C[pos].ans.clear();
		}
		else{
			R[pos].nadi(1, h, r, c == 'W');
			for(int x : R[pos].ans)
				R[pos].update(x), C[x].update(pos);
			R[pos].ans.clear();
		}
	}
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			vR[i][j] = R[i].T[R[i].off + j];
	for(int i = 0;i < n;i++)
		for(int j = 0;j < m;j++)
			vR[i][j] += (i ? vR[i - 1][j] : 0) + (j ? vR[i][j - 1] : 0) - (i && j ? vR[i - 1][j - 1] : 0); 
	int sol = 0;
	for(int i = 0;i + p <= n;i++)
		for(int j = 0;j + p <= m;j++)
			sol = max(sol, vR[i + p - 1][j + p - 1] - (i ? vR[i - 1][j + p - 1] : 0)
						 - (j ? vR[i + p - 1][j - 1] : 0) + (i && j ? vR[i - 1][j - 1] : 0));
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

ufo.cpp: In function 'int main()':
ufo.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d%d%d%d", &n, &m, &r, &q, &p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:52:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
ufo.cpp:61:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   char c; int pos, h; scanf(" %c%d%d", &c, &pos, &h);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 100