Submission #393443

#	Time	Username	Problem	Language	Result	Execution time	Memory
393443		patrikpavic2	UFO (IZhO14_ufo)	C++17	100 / 100	1147 ms	247320 KiB

ufo

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

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 1e6 + 500;

int n, m, r, q, p;


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 /= 2)
			T[i] = max(T[2 * i], T[2 * i + 1]);
	}
	vi ans; bool L; int x;
	void nadi(int i){
		if((int)ans.size() >= r) return;
		if(i >= off) {
			ans.PB(i - off);
			return;
		}
		if(T[2 * i] >= x && L)
			nadi(2 * i);
		if(T[2 * i + 1] >= x && (int)ans.size() < r)
			nadi(2 * i + 1);
		if(T[2 * i] >= x && (int)ans.size() < r && !L)
			nadi(2 * i);
	}
};

vi vR[N], vC[N];
tournament R[N], C[N];

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].x = h, C[pos].L = c == 'N';
			C[pos].nadi(1);
			for(int x : C[pos].ans)
				C[pos].update(x), R[x].update(pos);
			C[pos].ans.clear();
		}
		else{
			R[pos].x = h, R[pos].L = c == 'W';
			R[pos].nadi(1);
			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:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d%d%d%d%d", &n, &m, &r, &q, &p);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ufo.cpp:55:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |    int x; scanf("%d", &x);
      |           ~~~~~^~~~~~~~~~
ufo.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   char c; int pos, h; scanf(" %c%d%d", &c, &pos, &h);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100