Submission #393439

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
393439	2021-04-23T12:38:20 Z	patrikpavic2	UFO (IZhO14_ufo)	C++17	25 / 100	2000 ms	247244 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--)
			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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	172488 KB	Output is correct
2	Correct	93 ms	172588 KB	Output is correct
3	Correct	92 ms	172648 KB	Output is correct
4	Correct	112 ms	172804 KB	Output is correct
5	Execution timed out	2098 ms	174824 KB	Time limit exceeded
6	Correct	761 ms	189560 KB	Output is correct
7	Execution timed out	2101 ms	209056 KB	Time limit exceeded
8	Execution timed out	2101 ms	208632 KB	Time limit exceeded
9	Execution timed out	2096 ms	207580 KB	Time limit exceeded
10	Execution timed out	2087 ms	208992 KB	Time limit exceeded
11	Execution timed out	2091 ms	199992 KB	Time limit exceeded
12	Execution timed out	2091 ms	209036 KB	Time limit exceeded
13	Execution timed out	2069 ms	209000 KB	Time limit exceeded
14	Execution timed out	2097 ms	199752 KB	Time limit exceeded
15	Execution timed out	2095 ms	208624 KB	Time limit exceeded
16	Execution timed out	2099 ms	199752 KB	Time limit exceeded
17	Execution timed out	2070 ms	209000 KB	Time limit exceeded
18	Execution timed out	2106 ms	198084 KB	Time limit exceeded
19	Execution timed out	2101 ms	211752 KB	Time limit exceeded
20	Execution timed out	2074 ms	247244 KB	Time limit exceeded