Submission #393443

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393443	2021-04-23T12:56:51 Z	patrikpavic2	UFO (IZhO14_ufo)	C++17	100 / 100	1147 ms	247320 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	172560 KB	Output is correct
2	Correct	96 ms	172556 KB	Output is correct
3	Correct	91 ms	172552 KB	Output is correct
4	Correct	101 ms	172944 KB	Output is correct
5	Correct	160 ms	174856 KB	Output is correct
6	Correct	254 ms	189512 KB	Output is correct
7	Correct	354 ms	209220 KB	Output is correct
8	Correct	313 ms	208748 KB	Output is correct
9	Correct	453 ms	208144 KB	Output is correct
10	Correct	543 ms	209576 KB	Output is correct
11	Correct	407 ms	200040 KB	Output is correct
12	Correct	547 ms	209772 KB	Output is correct
13	Correct	665 ms	209868 KB	Output is correct
14	Correct	584 ms	200164 KB	Output is correct
15	Correct	682 ms	208740 KB	Output is correct
16	Correct	338 ms	199564 KB	Output is correct
17	Correct	928 ms	209396 KB	Output is correct
18	Correct	324 ms	198164 KB	Output is correct
19	Correct	427 ms	211928 KB	Output is correct
20	Correct	1147 ms	247320 KB	Output is correct