oj.uz

답안 #393439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393439 2021-04-23T12:38:20 Z patrikpavic2 UFO (IZhO14_ufo) C++17
25 / 100
 2000 ms 247244 KB 
#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

# 결과 실행 시간 메모리 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